LeetCode - Balanced Binary Tree

题目：

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

思路：

1) 计算结点的高度，但这个有重复计算

package tree;

public class BalancedBinaryTree {

    public boolean isBalanced(TreeNode root) {

        if (root == null) return true;

        int leftHeight = height(root.left);

        int rightHeight = height(root.right);

        return Math.abs(leftHeight - rightHeight) <= 1 &&

                isBalanced(root.left) && isBalanced(root.right);

    }

    private int height(TreeNode root) {

        if (root == null) return 0;

        return Math.max(1 + height(root.left), 1 + height(root.right));

    }

}

2) 不进行重复计算，但需要new 对象，反而也花时间

package tree;

public class BalancedBinaryTree {

    class Entry{

        public int height;

        public boolean balanced;

    }

    public boolean isBalanced(TreeNode root) {

        return checkTree(root).balanced;

    }

    private Entry checkTree(TreeNode root) {

        Entry entry = new Entry();

        if (root == null) {

            entry.height = 0;

            entry.balanced = true;

        } else {

            Entry left = checkTree(root.left);

            Entry right = checkTree(root.right);

            entry.height = Math.max(left.height, right.height) + 1;

            entry.balanced = Math.abs(left.height - right.height) <= 1 && left.balanced && right.balanced;

        }

        return entry;

    }

}

巴特西

LeetCode - Balanced Binary Tree

最新文章

热门文章