leetcode 530 二叉搜索树的最小绝对差

迷南。 2022-09-12 04:39 152阅读 0赞

## 前言 ##

题目：[530. 二叉搜索树的最小绝对差][530.]

参考题解：[530.二叉搜索树的最小绝对差-代码随想录][530._-]

--------------------

## 提交代码 ##

方法一：**线索二叉树的中序遍历结果为升序**。将中序遍历的结果放入vector中，然后顺序求差比较。

方法二：我们也可以边遍历，边比较。我们需要比较中序遍历过程中，相邻节点的差值。**重点在于递归过程中如何保存前一个节点的值**。参考题解的代码，具有借鉴意义。

方法一代码。

class Solution {
    public:
        void inorder_traverse(TreeNode* root, vector<int>& result){
            // 线索二叉树的中序遍历结果，为升序
            if(root == nullptr)
                return;
            inorder_traverse(root->left,result);
            result.push_back(root->val);
            inorder_traverse(root->right,result);
        }
    
        int getMinimumDifference(TreeNode* root) {
            vector<int> result;
            inorder_traverse(root,result);
            int min = INT_MAX;
            for(int i=1; i<result.size(); i++){
                if(result[i]-result[i-1] < min)
                    min = result[i]-result[i-1];
            }
            return min;
        }
    };

方法二代码。代码来自参考题解。

class Solution {
    private:
    int result = INT_MAX;
    TreeNode* pre;
    void traversal(TreeNode* cur) {
        if (cur == NULL) return;
        traversal(cur->left);   // 左
        if (pre != NULL){       // 中
            result = min(result, cur->val - pre->val);
        }
        pre = cur; // 记录前一个
        traversal(cur->right);  // 右
    }
    public:
        int getMinimumDifference(TreeNode* root) {
            traversal(root);
            return result;
        }
    };

[530.]: https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/
[530._-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.md