LeetCode 783. 二叉搜索树节点最小距离

2026-05-26 HGNULB 约 6 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 783. 二叉搜索树节点最小距离

题意分析

输入是一棵二叉搜索树，要求任意两个不同节点的值之差的最小绝对值。

「任意两个」听上去有 $O(n^2)$ 对要比，但输入不是随意一堆数，而是一棵二叉搜索树 —— 左子树的值全部小于根、右子树的值全部大于根。这条性质等价于说，所有节点值之间存在一个已经确定好的全序，只是没有被显式写出来。

目标是最小差，不是某一对具体节点，因此不需要记录是谁和谁，只要能不漏地考察所有「可能成为最小差」的数对即可。

约束上节点数只有 2 到 100，值域 $[0, 10^5]$，规模小到 $O(n^2)$ 也能过。真正值得注意的是值域下界是 0，任何拿 0 当哨兵的写法都会出事。题目保证至少两个节点，所以答案一定存在，不必处理无解分支。

解法：中序遍历

核心思路

最朴素的做法是把所有节点值收进一个数组，两两枚举求最小差，$O(n^2)$。

稍进一步：把数组排序后，只需比较相邻两项。理由是若 $a < b < c$，那么 $c - a$ 既大于 $b - a$ 也大于 $c - b$，跨项的差永远不可能是最小的。这样降到 $O(n \log n)$，瓶颈全在排序上。

而排序这一步恰恰是白做的：二叉搜索树的中序遍历本来就按升序输出所有节点值。既然有序序列已经免费到手，就没必要先物化成数组再排序，直接把「相邻比较」这个动作嵌进遍历过程即可。

于是维持这样一个不变量：中序遍历访问到节点 node 的那一刻，prev 恰好等于中序序列里 node 的直接前驱的值；如果 node 是整棵树中序序列的第一个节点，则 prev 尚未被赋值。有了它，node.val - prev 就是有序序列中相邻两项之差，因为序列升序所以这个减法天然非负，连绝对值都不用取。

解题步骤

准备两个跨递归层共享的状态：prev 表示上一个被访问节点的值（初始为「未设置」），answer 表示当前已知的最小差（初始为一个足够大的值）。它们必须是成员变量或闭包捕获的变量，不能作为按值传递的参数，否则右子树看不到左子树留下的前驱。

递归函数遇到空节点直接返回。这是中序遍历的出口，也保证叶子的左右孩子不会引发空指针。

先递归左子树。中序的顺序是「左、自己、右」，只有严格遵守这个顺序，prev 才真的是中序前驱。

回到当前节点时，若 prev 已被设置就用 node.val - prev 更新 answer。第一个被访问的节点没有前驱，必须靠「是否已设置」这个标记跳过，而不能靠某个具体数值判断 —— 值域含 0，任何数值哨兵都可能与真实值撞车。

然后立刻把 prev 更新成 node.val，再递归右子树。更新必须夹在两次递归之间：早于左子树会让当前节点和自己的祖先比，晚于右子树会让右子树里的节点拿到过期的前驱。

遍历结束返回 answer。

以 root = [4, 2, 6, 1, 3] 走一遍（根 4，左孩子 2 带 1 和 3 两个孩子，右孩子 6）：

从 4 出发先入左子树到 2，再入左子树到 1，1 的左孩子为空返回。访问节点 1 时 prev 尚未设置，跳过比较，令 prev = 1；1 的右孩子为空，返回。

回到节点 2，prev = 1，算出 2 - 1 = 1，answer 从初始大值更新为 1；令 prev = 2，进入 2 的右子树。

访问节点 3，prev = 2，算出 3 - 2 = 1，不小于 1 故 answer 保持 1；令 prev = 3。3 无子节点，返回。

回到根节点 4，prev = 3，算出 4 - 3 = 1，answer 仍为 1；令 prev = 4，进入右子树。

访问节点 6，prev = 4，算出 6 - 4 = 2，大于 1 故 answer 保持 1；令 prev = 6。

遍历结束返回 1。核对一下：中序序列是 1, 2, 3, 4, 6，相邻差依次为 1、1、1、2，最小值确实是 1，且访问顺序与上面逐步得到的 prev 完全对应。

代码实现

// 只需比较相邻元素差值的最小值。
class Solution {
    private Integer prev = null;
    private int answer = Integer.MAX_VALUE;

    public int minDiffInBST(TreeNode root) {
        inorder(root);
        return answer;
    }

    private void inorder(TreeNode node) {
        if (node == null) {
            return;
        }

        inorder(node.left);

        if (prev != null) {
            answer = Math.min(answer, node.val - prev);
        }
        prev = node.val;

        inorder(node.right);
    }
}

// 只需比较相邻元素差值的最小值。
func minDiffInBST(root *TreeNode) int {
    prevSet := false
    prev := 0
    answer := int(^uint(0) >> 1)

    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }

        inorder(node.Left)

        if prevSet {
            diff := node.Val - prev
            if diff < answer {
                answer = diff
            }
        }
        prev = node.Val
        prevSet = true

        inorder(node.Right)
    }

    inorder(root)
    return answer
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 为节点数。中序遍历访问每个节点恰好一次，每次只做常数次比较和赋值。

空间复杂度：$O(h)$，其中 $h$ 为树高，来自递归调用栈；平衡树为 $O(\log n)$，退化成链时最坏为 $O(n)$。没有额外保存完整中序序列。

关键点总结

BST 的中序遍历严格递增；有序序列的最小两数差必然出现在相邻元素之间，因此无需枚举所有节点对。

prev 的语义是“中序序列中刚刚访问的值”，必须在访问当前节点后、进入右子树前更新。

用可空变量或独立布尔值表示“尚无前驱”，不能拿 0 充当哨兵，因为 0 是合法节点值。

面试追问若要求 $O(1)$ 额外空间，可讨论 Morris 中序遍历；普通版本优先写清晰的 $O(h)$ 递归解法。

易错点总结

只比较父子节点而不是中序相邻节点：最小差的两个值不一定有直接父子关系。例如根为 100，左链上的搜索路径依次包含 50、90、99 时，最小差来自 99 与祖先 100，二者并非直接父子；只比较树边会漏掉答案 1。

用 prev = 0 判断是否存在前驱：根值域包含 0，树 [0,1] 会跳过差值 1；应使用 Integer prev = null 或 prevSet。

在递归左子树之前更新 prev：这会让 prev 表示祖先而非中序前驱，破坏有序相邻关系。

先递归右子树、最后才更新 prev：右子树会继续拿到左侧的旧值，同一个前驱被重复使用，可能得到错误差值。

相似题目

题目	难度	与本题的联系
530. 二叉搜索树的最小绝对差	简单	同题变体，可复用中序相邻比较
98. 验证二叉搜索树	中等	同样利用中序严格递增，但检查的是全局合法性
230. 二叉搜索树中第 K 小的元素	中等	中序序列的顺序统计问题