题目描述

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

思路

BST 的中序遍历结果是严格递增序列，相邻节点之差一定是所有节点对中最小的，因此只需要在中序遍历过程中比较当前节点与前一个节点的差值即可。

用 prenode 记录上一个访问节点的值，初始化为 math.MinInt / 2。不用 math.MinInt 是为了避免第一次做减法时发生整数溢出（node.Val - math.MinInt 会溢出）。每次访问当前节点时，用 node.Val - prenode 更新全局最小值，然后把 prenode 更新为当前节点值，继续遍历右子树。

知识边界

  • BST 中序遍历得到有序序列，是很多 BST 题目的核心性质，需要熟练掌握
  • prenode 初始化为 math.MinInt / 2 而非 math.MinInt，避免第一次相减时溢出

代码

import "math"
 
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func getMinimumDifference(root *TreeNode) int {
    ans := math.MaxInt
    prenode := math.MinInt / 2
 
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        dfs(node.Left)
        ans = min(ans, node.Val-prenode)
        prenode = node.Val
        dfs(node.Right)
    }
    dfs(root)
    return ans
}