LeetCode 530. 二叉搜索树的最小绝对差
目录
题目描述
题意分析
输入是一棵二叉搜索树，输出是「树中任意两个不同节点，值之差的绝对值」的最小可能取值。注意配对是任意的，两个节点之间不要求有祖先后代关系，也不要求同属一棵子树。
题目给出的最强约束是「二叉搜索树」这四个字。如果只说是普通二叉树，那就只能把所有值收集起来做全局比较；而搜索树意味着节点值之间存在一个已经排好的全序关系，这个关系可以直接从树的形状里读出来，不需要额外付出比较代价。这是本题唯一值得利用的信号。
边界方面：题目保证节点数至少为 2，所以答案一定存在，不必考虑「配不出一对」的情况；节点值互不相同不是题目承诺的前提，如果出现相同值，答案自然就是 0，算法也应当能自然得到这个结果。另外树可能退化成一条链，所以任何与树高相关的开销都要按最坏 $O(n)$ 估计。
解法：中序遍历比较相邻值
核心思路
若把所有节点值排成升序 $a_0,a_1,\ldots,a_{n-1}$，最小绝对差一定出现在相邻元素之间。因为对任意 $i<j$，都有
\[a_j-a_i \ge a_{i+1}-a_i\]二叉搜索树的中序遍历恰好得到升序序列，因此无需额外排序，也无需枚举所有节点对。
遍历时维护不变量：
prev是当前节点在中序序列中的直接前驱，ans是已访问前缀中所有相邻差的最小值。访问当前节点时，用node.val - prev更新答案，再推进prev。每个相邻对都会在访问后一项时被检查，而任何非相邻对都不可能更优，所以最终答案正确。使用“是否存在前驱”的独立状态，避免把合法节点值误作哨兵。
解题步骤
- 用显式栈执行中序遍历：不断压入当前节点的左链。
- 弹出栈顶，得到下一个升序节点。
- 若已经有前驱，用当前值减前驱值更新最小差。
- 把当前值保存为新前驱，然后转向右子树。
- 栈和游标都为空时返回答案。
例如
[4,2,6,1,3]的中序序列为1,2,3,4,6，只需比较差值1,1,1,2，最小值为 1。
代码实现
import java.util.ArrayDeque;
import java.util.Deque;
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)$，其中 $h$ 是树高；最坏退化为 $O(n)$。
关键点总结
- BST 的中序遍历把树问题转化成有序序列问题。
- 有序序列的最小差只可能来自相邻元素。
prev表示中序前驱，不是父节点。- 使用
null或额外布尔量区分“无前驱”，不要猜一个节点值之外的哨兵。
易错点总结
- 使用前序或后序遍历：访问序列无序，只比较相邻节点不再成立。
- 拿父节点当
prev：父节点不一定是中序直接前驱。- 用 0、-1 等合法值充当哨兵：第一次差值可能污染答案。
- 弹栈后忘记转向右子树：整棵右子树会被漏掉。
- 收集全部值后两两比较：正确但退化为 $O(n^2)$，没有利用有序性。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 783. 二叉搜索树节点最小距离 | 简单 | 同一模型的换皮题，可直接复用代码 |
| 94. 二叉树的中序遍历 | 简单 | 只要求输出序列本身，是本题的骨架 |
| 230. 二叉搜索树中第 K 小的元素 | 中等 | 中序过程中计数并提前终止 |
| 98. 验证二叉搜索树 | 中等 | 用中序前驱判断严格递增而非求差 |
| 501. 二叉搜索树中的众数 | 简单 | 中序过程中统计连续相等段的长度 |