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

leecode原题

题目

给你一个二叉搜索树的根节点 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

解题思路

思路

题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。

注意是二叉搜索树，二叉搜索树可是有序的。

遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值，这样就简单多了。

那么二叉搜索树采用中序遍历，其实就是一个有序数组。

实现

源码

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// 中序遍历
func inorderTravel(root *TreeNode, arr *[]int) {
    if root == nil {
        return
    }
    // 遍历左子树
    inorderTravel(root.Left, arr)
    // 访问根节点
    *arr = append(*arr, root.Val)
    // 遍历右子树
    inorderTravel(root.Right, arr)
}

func getMinimumDifference(root *TreeNode) int {
    // 利用二叉搜索树和中序遍历的特性，可以采用中序遍历，得到一个有序的数组
    arr := make([]int, 0)
    // 中序遍历后得到一个有序的数组
    inorderTravel(root, &arr)
    minValue := math.MaxInt64
    for i := 1; i < len(arr); i++ {
        sub := arr[i] - arr[i-1]
        if sub < 0 {
            sub = -sub
        }
        if sub < minValue {
            minValue = sub
        }
    }
    return minValue
}