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

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

树中节点的数目范围是 [2, 10⁴]
0 <= Node.val <= 10⁵

解法一：递归

错误代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


func getMinimumDifference(root *TreeNode) int {
    if root == nil {
        return math.MaxInt32
    }
    res := math.MaxInt32
    if root.Left != nil {
        res = min(res, abs(root.Val-root.Left.Val))
    }
    if root.Right != nil {
        res = min(res, abs(root.Val-root.Right.Val))
    }
    res = min(res, getMinimumDifference(root.Left))
    res = min(res, getMinimumDifference(root.Right))
    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func abs(num int) int {
    if num < 0 {
        return -num
    }
    return num
}

正确代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


type Result struct {
    diff   int
    minVal int
    maxVal int
}

func getMinimumDifference(root *TreeNode) int {
    if root == nil {
        return 0
    }
    var dfs func(root *TreeNode) *Result
    dfs = func(root *TreeNode) *Result {
        ret := &Result{}
        if root.Left == nil && root.Right == nil {
            // note: assign ret.diff to math.MaxInt32
            ret.diff, ret.minVal, ret.maxVal = math.MaxInt32, root.Val, root.Val
        } else if root.Left == nil {
            // root.Right != nil
            rightRes := dfs(root.Right)
            curDiff := min(rightRes.minVal-root.Val, rightRes.diff)
            ret.diff, ret.minVal, ret.maxVal = curDiff, root.Val, rightRes.maxVal
        } else if root.Right == nil {
            // root.Left != nil
            leftRes := dfs(root.Left)
            curDiff := min(root.Val-leftRes.maxVal, leftRes.diff)
            ret.diff, ret.minVal, ret.maxVal = curDiff, leftRes.minVal, root.Val
        } else {
            // root.Left != nil && root.Right != nil
            leftRes := dfs(root.Left)
            rightRes := dfs(root.Right)
            curDiff := min(root.Val-leftRes.maxVal, rightRes.minVal-root.Val, leftRes.diff, rightRes.diff)
            ret.diff, ret.minVal, ret.maxVal = curDiff, leftRes.minVal, rightRes.maxVal
        }
        return ret
    }
    return dfs(root).diff
}

func min(nums ...int) int {
    ret := nums[0]
    for _, num := range nums {
        if num < ret {
            ret = num
        }
    }
    return ret
}

解法二：中序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


func getMinimumDifference(root *TreeNode) int {
    // prev not in [0, 10^5]
    prev, res := -1, math.MaxInt32
    var inorder func(root *TreeNode)
    inorder = func(root *TreeNode) {
        if root == nil {
            return
        }
        inorder(root.Left)
        if prev != -1 {
            res = min(res, root.Val-prev)
        }
        prev = root.Val
        inorder(root.Right)
    }
    inorder(root)
    return res
}

func min(nums ...int) int {
    ret := nums[0]
    for _, num := range nums {
        if num < ret {
            ret = num
        }
    }
    return ret
}