86.二叉搜索树的最小绝对差
题目
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
- 输入：root = [4,2,6,1,3]
- 输出：1
示例 2：
- 输入：root = [1,0,48,null,null,12,49]
- 输出：1
提示：
- 树中节点的数目范围是 [2, 104]
- 0 <= Node.val <= 105
思路
- 第 0 步：暴力法（想一下就好，别真写）
把所有节点值收集起来，两两求差取最小。O(n²) 时间。能过（n ≤ 10^4），但完全浪费了"BST"这个条件。
- 第 1 步：先想清楚一件事——最小差一定来自"排序后相邻的两个数"
这是本题的核心洞察。
假设把所有值排成升序 a₀ < a₁ < a₂ < ... < aₙ₋₁。任取两个不相邻的数 aᵢ 和 aⱼ（j > i+1），它们的差是：
aⱼ - aᵢ = (aⱼ - aⱼ₋₁) + (aⱼ₋₁ - aᵢ)
≥ (aⱼ - aⱼ₋₁) ← 因为后一项必然 > 0
也就是说，跨过任何中间元素去比较，差值只会变大。所以最小差必然出现在排序后的相邻位置。
于是问题从"检查 n² 对"缩减到"检查 n-1 对"。
- 第 2 步：BST 送了你一个免费的有序数组
到这里如果是普通二叉树，你还得先把值收集起来排序，O(n log n)。
但这是 BST，它有一条铁律：
▎ 中序遍历（左 → 根 → 右）BST，得到的序列必然是严格升序的。
为什么？因为 BST 的定义就是"左子树全部 < 根 < 右子树全部"。
中序遍历恰好按这个顺序访问：先访问所有比我小的、再是我、再是所有比我大的。递归下去，整体就是升序。
4
/ \
2 6
/ \
1 3
中序遍历：1 → 2 → 3 → 4 → 6 ✅ 天然有序，不用排序。
- 第 3 步：合并成最终解法
最简单的算法就是中序遍历，然后把所有数据存数组，再循环遍历一遍找出相邻的最小的差就可以了，但是这样会造成空间复杂度对数组的浪费，完全可以用一个prev变量来记录上一个的值。
既然中序遍历直接给出升序序列，那就边遍历边比较相邻两个，连数组都不用存：
▎ 中序遍历，用一个变量 prev 记住上一个访问到的值。每到一个新节点，算 当前值 - prev，更新全局最小值。
为什么不用取绝对值？ 因为中序序列是升序的，当前值 - prev 必然 ≥ 0。这也是 BST 相比普通树省下来的一点好处。
于是每个节点的视角都极其简单：
4 ← 4 说："左边的 2 那一片先来（会给出 1,2,3），
/ \ 然后我，然后 6 那一片。"
2 6
/ \
1 3 ← 2 说："左边的 1 先来，然后我，然后右边的 3。"
1 说："左边空的，那就我，右边也空的。"
每个节点都在说同一句话。这就是递归。
class Solution2 {
fun getMinimumDifference(root: TreeNode?): Int {
val values = mutableListOf<Int>()
// 第 1 步：纯粹的中序遍历，把值按升序倒进数组，不掺任何业务逻辑
fun inorder(node: TreeNode?) {
if (node == null) return
inorder(node.left)
values.add(node.`val`) // 唯一的动作：记下来
inorder(node.right)
}
inorder(root)
// 第 2 步：现在 values 已经是升序数组了，问题变成"数组相邻两项最小差"
// 从下标 1 开始，和前一项比，完全没有递归了
var minDiff = Int.MAX_VALUE
for (i in 1 until values.size) {
minDiff = minOf(minDiff, values[i] - values[i - 1])
}
return minDiff
}
}
最好的写法:
class TreeNode(var `val`: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}
class Solution {
// 状态放在类上 —— 所有递归层访问的都是同一份
private var prev: Int? = null
private var minDiff = Int.MAX_VALUE
fun getMinimumDifference(root: TreeNode?): Int {
// ⚠️ 关键：入口处必须重置！
// 否则同一个 Solution 实例第二次被调用时，会带着上一次的残留状态
prev = null
minDiff = Int.MAX_VALUE
inorder(root)
return minDiff
}
// 独立的私有方法，不再嵌套
private fun inorder(node: TreeNode?) {
if (node == null) return
inorder(node.left) // ① 左
prev?.let { minDiff = minOf(minDiff, node.`val` - it) } // ② 根
prev = node.`val`
inorder(node.right) // ③ 右
}
}
复杂度
- 时间复杂度: O(n)
- 空间复杂度: O(h)
- 邮箱 ：charon.chui@gmail.com
- Good Luck!