algorithm/leetcode/MinimumDistanceBetweenBstNodes.java at master · skyczhao/algorithm · GitHub

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
package leetcode;

import utils.TreeNode;
import utils.Trees;

/**
 * MinimumDistanceBetweenBstNodes
 * https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
 * 783. 二叉搜索树节点最小距离
 * https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/solution/di-gui-chu-li-by-oshdyr-7vsc/
 *
 * @since 2021-04-13
 */
public class MinimumDistanceBetweenBstNodes {

    public static void main(String[] args) {
        MinimumDistanceBetweenBstNodes sol = new MinimumDistanceBetweenBstNodes();

        TreeNode head = Trees.fromIntegers(new Integer[]{27, null, 34, null, 58, 50, null, 44});
        System.out.println(sol.minDiffInBST(head));
    }

    class RangeResult {
        public int minDist;
        public int maxValue;
        public int minValue;

        public RangeResult(int minDist, int maxValue, int minValue) {
            this.minDist = minDist;
            this.maxValue = maxValue;
            this.minValue = minValue;
        }
    }

    public int minDiffInBST(TreeNode root) {
        return getMinDiff(root).minDist;
    }

    private RangeResult getMinDiff(TreeNode root) {
        if (root == null) {
            return null;
        }

        RangeResult res = new RangeResult(Integer.MAX_VALUE, root.val, root.val);

        RangeResult leftMin = getMinDiff(root.left);
        if (leftMin != null) {
            res.minValue = leftMin.minValue;
            int leftDist = root.val - leftMin.maxValue;
            if (leftDist < res.minDist) {
                res.minDist = leftDist;
            }
            if (leftMin.minDist < res.minDist) { // bug: 漏比较
                res.minDist = leftMin.minDist;
            }
        }

        RangeResult rightMin = getMinDiff(root.right);
        if (rightMin != null) {
            res.maxValue = rightMin.maxValue;
            int rightDist = rightMin.minValue - root.val;
            if (rightDist < res.minDist) {
                res.minDist = rightDist;
            }
            if (rightMin.minDist < res.minDist) { // bug: 漏比较
                res.minDist = rightMin.minDist;
            }
        }

        return res;
    }
}