530. 二叉搜索树的最小绝对差
#树 2024-11-13 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void transfer(TreeNode* root) {
        if(root == nullptr) return;
        transfer(root->left);
        data.push_back(root->val);
        transfer(root->right);
    }
    int getMinimumDifference(TreeNode* root) {
        transfer(root);
        int result = INT_MAX;
        for(int i = 1; i < data.size(); i++){
            result = min(result,abs(data[i] - data[i - 1]));
        }
        return result;
    }

private:
    vector<int> data;
};

这是最容易想到的版本，但我们可以在中序遍历的时候就进行差值，这样我们就可以避免后面的遍历一次数组的行为，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void transfer(TreeNode* cur) {
        if (cur == nullptr)
            return;
        transfer(cur->left);
        if (prev != nullptr) {
            result = min(result, abs(prev->val - cur->val));
        }
        prev = cur;
        transfer(cur->right);
    }
    int getMinimumDifference(TreeNode* root) {
        transfer(root);
        return result;
    }

private:
    int result = INT_MAX;
    TreeNode* prev = nullptr;
};

但是，我想讲一讲自己写代码犯下的错误，即在比较多过程中忽视掉了二叉搜索树的有序性，导致出现错误，这份错误代码核心部分如下：

1
2
3
4
5
6
void getMin(TreeNode * prev, TreeNode * cur) {
    if (cur == nullptr) return;
    target = min(target, abs(prev - >val - cur - >val));
    getMin(cur, cur - >left);
    getMin(cur, cur - >right);
}

它无法应对如下示例：

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

我的代码错就错在没有遵循二叉搜索树的有序性，让父节点和自己的子节点比较来获取最小的差值，这是错误的，如图中你无法获取 236 - 227 的差值，从而避开正确答案。

但如果按照前面提供的正确答案，而是 prev 节点 和 cur 节点比较就不会出错，因为在中序遍历下是有序的。而我的这份错误的代码的虽然也是中序，但是 prev 意指 父节点，而 cur 意指 孩子节点，这就无法完全遵循二叉搜索树的有序性，从而出错。