530. Minimum Absolute Difference in BST 

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
48
49
type Stack []*TreeNode

func (s *Stack) Push(node *TreeNode) {
    *s = append(*s, node)
}

func (s *Stack) Pop() *TreeNode {
    if len(*s) == 0 {
        return nil
    }

    lastIndex := len(*s) - 1
    last := (*s)[lastIndex]
    *s = (*s)[:lastIndex]
    return last
}

func (s *Stack) IsEmpty() bool {
    return len(*s) == 0
}

func getMinimumDifference(root *TreeNode) int {
    // 利用二叉搜索树中序遍历单调递增的特性来计算最小差值
    // left -> root -> right

    preVal, minDiff := math.MaxInt, math.MaxInt

    stack := Stack{}
    for !stack.IsEmpty() || root != nil {
        for root != nil {
            stack.Push(root)
            root = root.Left
        }

        // now: root is nil
        tmp := stack.Pop()

        if preVal != math.MaxInt {
            minDiff = min(minDiff, tmp.Val-preVal)
        }
        preVal = tmp.Val

        if tmp.Right != nil {
            root = tmp.Right
        }
    }

    return minDiff
}

References

530. Minimum Absolute Difference in BST
783. Minimum Distance Between BST Nodes