LeetCode 783. 二叉搜索树节点最小距离
题目描述
题意分析
在二叉搜索树中任选两个不同节点，求它们数值的最小绝对差。题目保证至少有两个节点；节点可以相距很远，不限于父子关系。可以利用二叉搜索树的大小关系避免枚举所有节点对。
解法：中序遍历
核心思路
[!blue]
二叉搜索树的中序遍历顺序是“左子树、根、右子树”，得到的节点值从小到大排列。在有序序列里，不相邻两个值之差等于它们之间所有相邻差之和，不会小于这些相邻差中的最小值，因此全局最小差一定能在某对相邻值中取得。
遍历时不必保存完整序列，只需保留上一个已访问值
prev。左子树处理完后，prev就是当前节点的中序前驱；若它存在，用node.val-prev更新answer，再让当前值成为新的前驱，继续处理右子树。
prev必须跨递归调用共享，才能比较跨越子树边界的相邻节点。每对中序相邻值恰好在访问后一个节点时比较一次，所以遍历结束后的最小差就是答案。第一个节点没有前驱，只负责初始化prev。
解题步骤
- 每次入口调用先清空前驱标记，把
answer设为足够大的初始值。- 递归遇到空节点直接返回；否则先遍历左子树。
- 前驱存在时，用当前值减去前驱值更新
answer。- 将当前值写入
prev，再遍历右子树；整棵树处理完后返回答案。0 是合法节点值，不能用它表示“没有前驱”：Java 用
null区分，Go 用prevSet标记。题目至少有两个节点，遍历一定会产生有效差值；Java 的成员状态在每次入口重置，复用对象时也不会带入上一棵树的数据。
代码实现
class Solution {
private Integer prev = null;
private int answer = Integer.MAX_VALUE;
public int minDiffInBST(TreeNode root) {
// 一次调用的前驱与答案从入口重新初始化
prev = null;
answer = Integer.MAX_VALUE;
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)$，每个节点只访问一次，并进行常数次比较。
- 空间复杂度：$O(h)$，递归栈深度等于树高；树退化成链时为 $O(n)$，除此之外只保留前驱和答案。
关键点总结
[!green]
- 前驱是中序前驱，不一定是父节点。
- 零是合法值，不能同时表示没有前驱。
易错点总结
[!yellow]
- 只比较父子节点，会漏掉其他相邻值。
- 先覆盖前值再比较，会与自身得到零差。
- Java 对象复用时不重置状态，会混入旧结果。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1200. 最小绝对差 | 简单 | 最小绝对差来自有序相邻值，本题中序天然有序，原题需先排序数组。 |
| 230. 二叉搜索树中第 K 小的元素 | 中等 | 同样沿BST中序按序读取，本题保留前一值求差，原题计数到第k项。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！