Minimum Absolute Difference In BST

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

分析

中序遍历：
- 按左子树 → 根节点 → 右子树的顺序遍历树，使得节点值按从小到大的顺序访问
计算最小差值：
- 在遍历过程中，记录上一个节点值 last
- 对当前节点值 root->val 和 last 计算差值，并更新最小差值 res
初始化：
- 使用一个布尔变量 firsted 标记是否是第一次访问节点，用于跳过第一个节点的差值计算
返回结果：
- 中序遍历完成后，res 即为任意两节点值之间的最小差值

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(logn)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution
{
public:
    int res = INT_MAX; // 最小差值的初始化
    int last;          // 上一个访问的节点值
    bool firsted = true; // 是否是第一个访问的节点

    int getMinimumDifference(TreeNode* root)
    {
        dfs(root); // 中序遍历
        return res;
    }

    void dfs(TreeNode* root)
    {
        if (!root)
            return;

        // 遍历左子树
        dfs(root->left);

        // 访问当前节点
        if (firsted)
            firsted = false; // 标记第一个节点
        else
            res = std::min(res, root->val - last); // 更新最小差值
        last = root->val; // 更新上一个节点值

        // 遍历右子树
        dfs(root->right);
    }
};