LeetCode第783题 – 二叉搜索树节点最小距离

题目

解答

方案一

class Solution {
    private List<Integer> values = new ArrayList<>();

    public void inorder(TreeNode node) {
        if (node == null) {
            return;
        }

        inorder(node.left);
        values.add(node.val);
        inorder(node.right);
    }

    public int minDiffInBST(TreeNode root) {
        inorder(root);

        int min = Integer.MAX_VALUE;
        for (int i = 1, length = values.size(); i < length; ++i) {
            min = Math.min(Math.abs(values.get(i) - values.get(i - 1)), min);
        }
        return min;
    }
}

方案二

class Solution {
    private int last = 0;
    private int min = Integer.MAX_VALUE;

    public void inorder(TreeNode node) {
        if (node == null) {
            return;
        }

        inorder(node.right);
        min = Math.min(Math.abs(last - node.val), min);
        last = node.val;
        inorder(node.left);
    }

    public int minDiffInBST(TreeNode root) {
        inorder(root);

        return min;
    }

}

要点
二叉搜索树，左子节点的值小于父节点的值，右子节点的值大于父节点的值，因而按照中序遍历树时，可以得到升序的排序结果，此时再对相邻两个数值进行求差运算，即得到最小的差。