LeetCode - Balanced Binary Tree

时间:2022-02-24 12:15:33

题目:

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