leetcode-530-easy

Minimum Absolute Difference in BST

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:

Input: root = [4,2,6,1,3]
Output: 1
Example 2:

Input: root = [1,0,48,null,null,12,49]
Output: 1
Constraints:

The number of nodes in the tree is in the range [2, 104].
0 <= Node.val <= 105
Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/

思路一：利用平衡二叉树有序的特点，使用中序遍历，依次对比

    private static int lastNum = -1;
    private static int minGap = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        lastNum = -1;
        minGap = Integer.MAX_VALUE;
        getMinimumDifferenceRec(root);
        return minGap;
    }

    public void getMinimumDifferenceRec(TreeNode root) {
        if (root == null) {
            return;
        }

        getMinimumDifferenceRec(root.left);
        if (lastNum == -1) {
            lastNum = root.val;
        } else {
            minGap = Math.min(minGap, root.val - lastNum);
            lastNum = root.val;
        }
        getMinimumDifferenceRec(root.right);
    }