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

85 views

题目

解答

方案一

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;
    }

}

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



若非注明,均为原创,欢迎转载,转载请注明来源:LeetCode第783题 – 二叉搜索树节点最小距离

关于 JackieAtHome

基层程序员,八年之后重新启航

此条目发表在 Java, LeetCode 分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Protected with IP Blacklist CloudIP Blacklist Cloud