530. Minimum Absolute Difference in BST
程序员文章站
2022-03-07 18:21:55
...
用vector< int >res装入BST的值,再对res处理得到绝对值最小的值。
int getMinimumDifference(TreeNode* root) {
vector<int> res;
bianLi(root,res);
int min=INT_MAX,n=res.size();
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
int tmp=abs(res[i]-res[j]);
min=tmp<min?tmp:min;
}
}
return min;
}
void bianLi(TreeNode* root,vector<int>& res){
if(!root) return ;
res.push_back(root->val);
bianLi(root->left,res);
bianLi(root->right,res);
}
根据BST的性质得到左<中<右,根据中序遍历得到一个有序数组,最小的绝对值在相邻值之间的差。因为题目中说明val为正值,可以用pre=-1来判断访问的前一个值是否存在。若值为整数,则应该通过访问的前一个节点是否为空来判断当前节点是否是第一个。
int getMinimumDifference(TreeNode* root) {
int res=INT_MAX,pre=-1;
inorder(root,pre,res);
return res;
}
void inorder(TreeNode* root,int &pre,int &res){
if(!root) return ;
inorder(root->left,pre,res);
if(pre!=-1) res=min(res,root->val-pre);
pre=root->val;
inorder(root->right,pre,res);
}
通过指针判断是否是第一个
int getMinimumDifference(TreeNode* root) {
TreeNode* pre=NULL;
int res=INT_MAX;
travPreorder(root,pre,res);
return res;
}
void travPreorder(TreeNode* root,TreeNode* &pre,int& res){
if(!root) return ;
travPreorder(root->left,pre,res);
if(pre!=NULL) res=min(res,(root->val)-(pre->val));
pre=root;
travPreorder(root->right,pre,res);
}
使用迭代的方式
int getMinimumDifference(TreeNode* root) {
int res=INT_MAX;
stack<TreeNode*>s;
TreeNode* pre=NULL;
while(true){
goAlongLeftPath(root,s);
if(s.empty()) break;
root=s.top();
s.pop();
if(pre!=NULL) res=min(res,root->val-pre->val);
pre=root;
root=root->right;
}
return res;
}
void goAlongLeftPath(TreeNode* root,stack<TreeNode*> &s){
while(root){
s.push(root);
root=root->left;
}
}
另一种迭代方式
int getMinimumDifference(TreeNode* root) {
int res=INT_MAX;
int pre=-1;
stack<TreeNode*>s;
while(root||!s.empty()){
while(root){
s.push(root);
root=root->left;
}
root=s.top();
s.pop();
if(pre!=-1) res=min(res,root->val-pre);
pre=root->val;
root=root->right;
}
return res;
}
可以用先序遍历
int getMinimumDifference(TreeNode* root) {
int res=INT_MAX;
helper(root,INT_MIN,INT_MAX,res);
return res;
}
void helper(TreeNode* root,int low,int high,int&res){
if(!root) return ;
if(low!=INT_MIN) res=min(res,root->val-low);
if(high!=INT_MAX) res=min(res,high-root->val);
helper(root->left,low,root->val,res);
helper(root->right,root->val,high,res);
}
上一篇: MySQL数据库高级查询和多表查询
下一篇: win10系统如何关闭软驱?
推荐阅读
-
530. Minimum Absolute Difference in BST
-
Leetcode每日一题:530.minimum-absolute-difference-in-bst(二叉搜索树的最小绝对值)
-
530. Minimum Absolute Difference in BST
-
LC-Minimum Absolute Difference in BST
-
(Java)leetcode-530 Minimum Absolute Difference in BST (二叉搜索树的最小绝对差)
-
LeetCode之路:530. Minimum Absolute Difference in BST
-
530 - 二叉搜索树的最小绝对差(minimum-absolute-difference-in-bst)
-
530. Minimum Absolute Difference in BST
-
LeetCode 530. Minimum Absolute Difference in BST
-
Leetcode 530. Minimum Absolute Difference in BST