如何求二叉搜索树中任意两个节点值的最小绝对差？

简化版

BST 中序遍历得到升序序列，任意两个节点的最小差一定出现在相邻元素之间。因此中序遍历时只比较当前值和前一个值，更新最小差即可。

详细版

普通做法是把所有节点值放进数组排序，再比较相邻值，时间 O(n log n)。但 BST 的中序遍历已经有序，所以排序可以省掉。

遍历时维护：

prev：中序序列中的前一个值；
ans：当前最小绝对差。

每访问一个节点：

若 prev 不为空，计算 node.val - prev；
用它更新 ans；
把 prev 改成当前值；
继续遍历右子树。

时间复杂度 O(n)，递归栈空间 O(h)。如果 BST 允许重复值，最小差可能为 0，算法也能处理。

完整版教学

一、为什么最小差只需要看中序相邻元素

在一个有序数组中，最小绝对差一定出现在相邻元素之间。原因很简单：如果有 a < b < c，那么 c-a = (b-a)+(c-b)，一定不小于 b-a 或 c-b 中较小的那个。因此跨过中间元素的差值不可能比所有相邻差更小。

BST 的中序遍历正好给出升序序列。于是树上的任意两点问题，被转换成有序序列的相邻差问题。我们不需要两两比较 O(n²)，也不需要额外排序 O(n log n)，只要中序扫一遍。

记忆钩子：有序序列里「最近」只能发生在邻居之间；BST 中序就是帮你把所有节点排成一条街。

二、带数字推演一遍

假设 BST 的中序结果是 [1, 3, 6, 10, 11, 15]。相邻差分别是：

3-1=2
6-3=3
10-6=4
11-10=1
15-11=4
min = 1

如果你试图比较 1 和 11，差是 10，显然不会比中间某一段相邻差更小。这个推演说明「只比较 prev」不是偷懒，而是数学上足够。

三、代码实现的关键变量

中序遍历时，只需要保存前一个访问值 prev。第一次访问时没有前驱，不能计算差；从第二个节点开始，当前值一定大于等于 prev，所以差值可写成 node.val - prev。

Integer prev = null;
int ans = Integer.MAX_VALUE;

int getMinimumDifference(TreeNode root) {
    inorder(root);
    return ans;
}

void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    if (prev != null) {
        ans = Math.min(ans, node.val - prev);
    }
    prev = node.val;
    inorder(node.right);
}

如果节点值可能接近整数边界，可以用 long 保存差值。多数算法题节点值范围较小，但讲清这个风险会显得更严谨。

四、为什么不能用前序或后序

前序和后序不保证访问值有序，所以「当前值和上一个值」不一定是数值意义上的邻居。比如同一棵 BST，中序可能是 [1,2,3,4]，前序可能是 [3,1,2,4]。前序里 3 和 1 相邻，但中间其实还有 2，它们不是排序后的邻居。

对比一下：

遍历方式	是否有序	能否只比较前一个访问值	原因
中序	是	可以	相邻访问就是排序相邻
前序	否	不可以	根先访问，顺序与大小无关
后序	否	不可以	子树先访问，顺序与大小无关

所以这题表面是求差值，实际考点是「你是否知道 BST 中序的有序性，以及能否把有序性用于证明」。

五、边界情况和题目假设

如果树少于 2 个节点，严格来说没有任意两个节点的差值；很多平台保证至少 2 个节点。工程实现中可以在入口处判断，少于 2 个节点时抛异常或返回约定值。面试时要先听清题目约束，不要在无定义场景里随便返回 0。

如果 BST 允许重复值，两个相同值节点的最小绝对差为 0。中序遍历里它们会连续出现，node.val - prev 得到 0，算法自然能发现。这也说明代码不能假设差值一定为正。

六、复杂度与优化空间

算法访问每个节点一次，时间 O(n)。递归栈空间 O(h)，平衡树时 O(log n)，退化成链表时 O(n)。如果需要降低栈空间，可以用迭代中序显式栈；空间数量级仍是 O(h)。若进一步要求 O(1) 额外空间，可以用 Morris 中序遍历。

平衡 BST: h≈log2(n)，n=1024 时 h≈10
退化 BST: h=n，n=1024 时 h=1024

复杂度里最容易说错的是把它讲成 O(n log n)。那是「先收集再排序」的普通树思路，不是利用 BST 后的最优思路。

七、常见误区与追问

误区：任意两点最小差需要双重循环。 有序性把候选压缩到相邻元素，双重循环是没利用 BST。
追问：为什么跨相邻元素不会更小？ 因为跨越差等于多段相邻差之和，不可能小于其中所有单段。
误区：前序遍历也能比较上一个节点。 前序相邻不代表数值相邻，比较会漏掉真正最小差。
追问：重复值怎么处理？ 重复值连续出现，差值为 0，算法自然返回 0。
误区：递归中序空间是 O(1)。 递归栈仍然占 O(h)，只有 Morris 才能做到严格 O(1) 额外空间。

八、加强记忆

这题可以抓住两个关键词：中序、有序邻居。BST 中序生成升序序列，有序序列的最小差只会出现在相邻元素之间，所以遍历时保存 prev 就够了。不要被「任意两个节点」吓到，任意只是原题描述，真正候选被有序性压缩成 n-1 个相邻差。面试回答时最好补上证明，这比只写代码更能体现理解。

简化版

详细版