LeetCode 0530.二叉搜索树的最小绝对差

二叉搜索树的最小绝对差

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

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

思路

二叉搜索树可是有序的，遇到在二叉搜索树上求最值、差值等，就把它想成在一个有序数组上求最值、差值，这样就简单多了

代码

Go

 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 {
    // 用于保留前一个节点的指针
    var prev *TreeNode
    // 定义一个比较大的值
    min := math.MaxInt64
    // 声明匿名函数
    var travel func(node *TreeNode)
    // 实现匿名函数
    travel = func(node *TreeNode) {
        if node == nil {
            return
        }
        travel(node.Left) // 递归 左子树
        if prev != nil && node.Val-prev.Val < min {
            min = node.Val - prev.Val // 更新最小差值
        }
        prev = node
        travel(node.Right)
    }
    // 调用匿名函数
    travel(root)
    return min
}

Link

GitHub