Adrian Wang's blog

一个完全由AI生成，但是内容高质量的Blog

LeetCode 530 - 二叉搜索树的最小绝对差（Minimum Absolute Difference in BST）

Posted on Edited on In , ,
Symbols count in article: 1.9k Reading time ≈ 2 mins.
利用二叉搜索树中序遍历有序性的特点，通过一次遍历找出相邻节点的最小绝对差值，时间复杂度 O(n)，空间复杂度 O(h)

问题描述

给你一个二叉搜索树的根节点 root，返回 树中任意两不同节点值之间的最小差值。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1:

1
2
输入：root = [4,2,6,1,3]
输出：1

示例 2:

1
2
输入：root = [1,0,48,null,null,12,49]
输出：1

约束条件：

  • 树中节点的数目范围是 [2, 10^4]
  • 0 <= Node.val <= 10^5

注意： 本题与 783 题相同。

解题思路

这道题的核心思路是利用 二叉搜索树中序遍历的有序性。

关键洞察

二叉搜索树的中序遍历结果是一个有序序列。这意味着如果我们按照中序遍历访问节点，相邻访问的两个节点在数值上也是相邻的，因此最小差值一定出现在相邻的两个节点之间。

算法思路

我们不需要将中序遍历的结果存储到数组中，而是可以在遍历的过程中：

  1. 使用一个 prev 指针记录前一个访问的节点
  2. 使用一个 cur 指针记录当前访问的节点
  3. 在每次访问当前节点时，计算与前一个节点的差值
  4. 维护一个全局最小值

实现步骤

  1. 初始化：设置最小值为最大整数，前驱节点为空
  2. 中序遍历：左 → 根 → 右的顺序访问
  3. 处理当前节点：
    • 如果前驱节点不为空，计算差值并更新最小值
    • 将当前节点设为前驱节点
  4. 继续遍历右子树

实现细节

中序遍历的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func dfs(node *TreeNode) {
    if node == nil {
        return
    }
    
    dfs(node.Left)   // 遍历左子树
    
    // 处理当前节点
    cur = node
    if prev != nil {
        minVal = min(minVal, int(math.Abs(float64(prev.Val)-float64(cur.Val))))
    }
    prev = cur
    
    dfs(node.Right)  // 遍历右子树
}

为什么使用中序遍历？

对于二叉搜索树 [4,2,6,1,3]：

1
2
3
4
5
    4
   / \
  2   6
 / \
1   3

中序遍历序列：1 → 2 → 3 → 4 → 6

这是一个有序序列，最小差值只可能出现在相邻元素之间：

  • |2-1| = 1
  • |3-2| = 1
  • |4-3| = 1
  • |6-4| = 2

所以最小差值是 1。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func getMinimumDifference(root *TreeNode) int {
    minVal := math.MaxInt32
    var prev, cur *TreeNode
    
    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        
        dfs(node.Left)   // 遍历左子树
        
        cur = node
        if prev != nil {
            minVal = min(minVal, int(math.Abs(float64(prev.Val)-float64(cur.Val))))
        }
        prev = cur
        
        dfs(node.Right)  // 遍历右子树
    }
    
    dfs(root)
    return minVal
}

执行过程示例

以 [4,2,6,1,3] 为例：

1
2
3
4
5
6
7
8
9
访问顺序：1 → 2 → 3 → 4 → 6

1. 访问节点1：prev=nil, cur=1, prev=1
2. 访问节点2：prev=1, cur=2, 计算|2-1|=1, minVal=1, prev=2
3. 访问节点3：prev=2, cur=3, 计算|3-2|=1, minVal=1, prev=3  
4. 访问节点4：prev=3, cur=4, 计算|4-3|=1, minVal=1, prev=4
5. 访问节点6：prev=4, cur=6, 计算|6-4|=2, minVal=1, prev=6

最终结果：1

复杂度分析

时间复杂度： $O(n)$

  • 需要访问每个节点一次，其中 n 是树中节点的数量

空间复杂度： $O(h)$

  • 递归调用的栈深度等于树的高度 h
  • 最坏情况下（退化为链表）：$O(n)$
  • 最好情况下（平衡树）：$O(\log n)$

关键收获

  1. BST 性质的应用：二叉搜索树的中序遍历产生有序序列，这是解决此类问题的关键
  2. 空间优化：不需要额外数组存储遍历结果，一次遍历即可完成
  3. 算法模式：这种"在遍历过程中维护前驱节点"的模式在很多树问题中都很有用
  4. 相关问题：
    • LeetCode 783: 二叉搜索树节点最小距离（完全相同）
    • LeetCode 98: 验证二叉搜索树
    • LeetCode 230: 二叉搜索树中第K小的元素

常见陷阱

  1. 忘记初始化：prev 必须初始化为 nil
  2. 类型转换：Go 中需要将 int 转换为 float64 才能使用 math.Abs
  3. 遍历顺序：必须是中序遍历，其他遍历方式无法保证有序性