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

约 5 分钟
文章信息 10 个分类 5 个标签
分类
LeetCode CodeTop 简单 未解决 5-10 面试经典 150 题 腾讯 字节 阿里 猿辅导
标签
深度优先搜索 树 广度优先搜索 二叉树 二叉搜索树

题目描述

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

image-20260928235747970

image-20260928235747971

题意分析

在二叉搜索树中选择两个不同节点，使它们的节点值之差的绝对值最小，返回这个差值。两个节点不必有父子关系，也不要求位于同一侧子树。

题目保证至少有两个节点，节点值范围为 0..100000，因此一定存在可比较的节点对。只返回最小差，不需要记录是哪两个节点。

解法：中序遍历比较相邻值

核心思路

[!blue]

二叉搜索树的左子树值小、右子树值大，按左子树、当前节点、右子树的中序顺序访问，就能直接得到有序的节点值，无需额外收集后排序。

在有序序列中，任意两个不相邻值的差，都等于它们之间若干个非负相邻差之和，不可能小于其中最小的相邻差。因此全局最小绝对差一定能在某一对中序相邻节点间取得，只需保存上一个访问值 prev。

用栈模拟中序遍历：先沿左孩子不断入栈，走到空处后弹出一个节点，此时它的整个左子树已访问完，轮到访问它。将当前值减去 prev 更新答案，再保存当前值，最后转向右子树并继续沿左链下降。

prev 是中序访问顺序中的前驱，可能来自当前节点的左子树，也可能是某个祖先，不能替换成父节点。第一个被访问节点没有前驱，Java 用空引用、Go 用 hasPrev 区分，避免把任意初始数值误当作树中节点。

栈空且当前节点也为空时，全部节点都已按序访问。整个过程中只保留遍历栈、前驱值与最小差，无需保存完整有序序列，也不修改树。

解题步骤

  1. 初始化空栈、当前节点为根、前驱为尚不存在，最小差为最大整数。
  2. 当前节点非空时，不断入栈并转向左孩子。
  3. 弹出栈顶作为下一个中序节点；已有前驱时，用当前值减前驱更新最小差。
  4. 比较完成后将当前值保存为前驱，再转向右孩子。
  5. 重复到当前节点为空且栈也为空，返回最小差。

代码实现

class Solution {
    public int getMinimumDifference(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        Integer prev = null;
        int ans = Integer.MAX_VALUE;

        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }

            node = stack.pop();

            // 与中序访问前驱比较，不是与父节点比较
            if (prev != null) {
                ans = Math.min(ans, node.val - prev);
            }

            // 完成差值计算后再更新前驱
            prev = node.val;
            node = node.right;
        }

        return ans;
    }
}

func getMinimumDifference(root *TreeNode) int {
    stack := make([]*TreeNode, 0)
    node := root
    prev, ans := 0, int(^uint(0)>>1)
    hasPrev := false

    for node != nil || len(stack) > 0 {
        for node != nil {
            stack = append(stack, node)
            node = node.Left
        }

        node = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        // 与中序访问前驱比较，不是与父节点比较
        if hasPrev && node.Val-prev < ans {
            ans = node.Val - prev
        }
        // 完成差值计算后再更新前驱
        prev, hasPrev = node.Val, true
        node = node.Right
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(n)$，节点各入栈、出栈一次。
  • 空间复杂度：$O(h)$，保存待访问的祖先链。

关键点总结

[!green]

  • BST 的中序有序性把任意节点对问题缩减为相邻访问值的比较。
  • 相邻指中序顺序相邻，不是树上的边相连。
  • 先计算差再更新前驱，第一次访问只建立前驱。
  • 栈保存尚待访问的祖先，额外空间随树高增长。

易错点总结

[!yellow]

  • 只比较父子节点，会遗漏中序相邻却没有直接连边的节点对。
  • 比较前覆盖 prev，会把当前值与自身相减，错误得到零。
  • 不能把 prev 的任意初值直接当成有效前驱，需要单独标记是否已经访问过节点。
  • 最小差不能初始化为零，否则后续正差无法更新。
  • 外层循环需要同时检查当前节点和栈，当前节点为空时栈中仍可能有待访问的祖先。

相似题目

题目 难度 关联与区别
1200. 最小绝对差 简单 最小绝对差来自有序相邻值，本题由BST中序直接获得顺序，原题需先排序数组。
230. 二叉搜索树中第 K 小的元素 中等 同样利用中序有序性，原题按名次取节点，本题比较相邻访问值的差。
98. 验证二叉搜索树 中等 通过中序访问利用二叉搜索树的升序性质；本题比较相邻中序值的差，该题验证整个序列严格递增。
99. 恢复二叉搜索树 中等 通过中序访问利用二叉搜索树的升序性质；本题比较相邻中序值的差，该题根据下降位置定位交换节点。
173. 二叉搜索树迭代器 中等 通过中序访问利用二叉搜索树的升序性质；本题比较相邻中序值的差，该题用栈保存尚未访问的后续节点。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/70595944
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！