leetcode-783-easy

Minimum Distancd Between Nodes

Given the root of a Binary Search Tree (BST), return the minimum 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, 100].
0 <= Node.val <= 105
Note: This question is the same as 530: https://leetcode.com/problems/minimum-absolute-difference-in-bst/

思路一：先用中序遍历收集节点，然后依次对比

    List<Integer> minDiffInBSTList = new ArrayList<>();
    public int minDiffInBST(TreeNode root) {
        minDiffInBSTRec(root);
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < minDiffInBSTList.size(); i++) {
            min = Math.min(Math.abs(minDiffInBSTList.get(i) - minDiffInBSTList.get(i - 1)), min);
        }

        return min;
    }

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

        minDiffInBST(root.left);
        minDiffInBSTList.add(root.val);
        minDiffInBST(root.right);
    }

思路二：看了一下官方解答，发现用中序遍历记录前一个值，依次对比就行

    private  int minDiffInBSTVal = Integer.MAX_VALUE;
    private  int minDiffInBSTPre = -1;
    public  int minDiffInBST(TreeNode root) {
        minDiffInBSTRec(root);

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

        minDiffInBSTRec(root.left);
        if (minDiffInBSTPre == -1) {
            minDiffInBSTPre = root.val;
        } else {
            minDiffInBSTVal = Math.min(minDiffInBSTVal, root.val - minDiffInBSTPre);
            minDiffInBSTPre = root.val;
        }
        minDiffInBSTRec(root.right);
    }