balanced binary tree


Balanced Binary Tree
关键点在于减少重复计算。如果当前的子树不平衡,直接返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean (TreeNode root) {
return getHeight(root) != -1;
}

public int getHeight(TreeNode root) {
if (root == null)
return 0;
int left = getHeight(root.left);
if (left == -1)
return -1;
int right = getHeight(root.right);
if (right == -1)
return -1;
if (Math.abs(right - left) > 1)
return -1;
return Math.max(left, right) + 1;
}