欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

530. Minimum Absolute Difference in BST

程序员文章站 2022-03-07 18:21:55
...

530. Minimum Absolute Difference in BST
530. Minimum Absolute Difference in BST
用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);
    }