Check Balanced: Implement a function to check if a binary tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.
Hints:#21, #33, #49, #105, #124
解法1 - 深度优先（审题错误）
平衡的定义是一颗树中任意节点的两颗子树高度不的超过1。比如下面就是平衡的：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
1
/
2
1
/ \
2 3
1
/ \
2 3
/ \
4 5
|
下面是不平衡的：
1
2
3
4
5
6
7
|
1
/ \
2 3
/ \
4 5
/
6
|
可以看到（2）这个子树的高度是3，而（3）这个子树的高度是1，高度相差2，所以不平衡。
首先想到的是计算左右子树高度，然后判断差是否超过1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public boolean checkBalanced(Node root) {
int lHeight = height(root.left);
int rHeight = height(root.right);
return Math.abs(lHeight - rHeight) <= 1;
}
private int height(Node node) {
if (node == null) {
return 0;
}
int lHeight = height(node.left);
int rHeight = height(node.right);
return Math.max(lHeight, rHeight) + 1;
}
|
解法2 - 广度优先（审题错误）
解法1是深度优先的，他会遍历到所有节点，是否可以用广度优先的算法来解。
因为广度优先是一层一层遍历的，在遍历过程中记录第一个叶子节点的层数，并且比较当前遍历的层数的差，超过1就说明不平衡：
1
2
3
4
5
6
7
|
1
/ \
2 3 <- 叶子节点
/ \
4 5
/
6 <- 当前层
|
这样就不需要遍历所有节点了。
要注意以下处理这种情况：
1
2
3
4
5
6
7
|
1
/
2
/
3
/
4
|
这种情况下可以认为叶子节点的层数为1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
public boolean checkBalanced(Node root) {
int firstLeafLevel = 0;
if (root.left == null || root.right == null) {
firstLeafLevel = 1;
}
int currentLevel = 1;
List<Node> current = new ArrayList<>();
current.add(root);
while (!current.isEmpty()) {
if (currentLevel - firstLeafLevel > 1) {
return false;
}
List<Node> parent = current;
current = new ArrayList<>();
for (Node p : parent) {
if (p.left != null) {
current.add(p.left);
}
if (p.right != null) {
current.add(p.right);
}
if (firstLeafLevel != 0 && p.left == null && p.right == null) {
// 第一个叶子节点的深度
firstLeafLevel = currentLevel;
}
}
if (!current.isEmpty()) {
current.level++;
}
}
return true;
}
|
解法3
上面两个解法审题错误，从根节点来看左右子树高度不超过1不代表左子树的左右子树高度不超过1。所以要对每个节点都计算一下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public boolean checkBalanced(Node root) {
int lHeight = height(root.left);
int rHeight = height(root.right);
if (Math.abs(lHeight - rHeight) <= 1) {
return true;
}
return checkBalanced(root.left) && checkBalanced(root.right);
}
private int height(Node node) {
if (node == null) {
return 0;
}
int lHeight = height(node.left);
int rHeight = height(node.right);
return Math.max(lHeight, rHeight) + 1;
}
|
解法4
但是上面牵涉到很多重复计算，那么可以在计算height的时候就同时判断是否平衡：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Tmp {
int height;
boolean balanced;
}
public Tmp height(Node node) {
if (node == null) {
return new Tmp(0, true);
}
Tmp l = height(node.left);
if (!l.balanced) {
return false;
}
Tmp r = height(node.right);
if (!r.balanced) {
return false;
}
int h = Math.max(l.height, r.height) + 1;
if (Math.abs(l.height - r.height) > 1) {
return new Tmp(h, false);
}
return new Tmp(h, true);
}
|
其实还可以更简单一点，用异常：
1
2
3
4
5
6
7
8
9
10
11
|
public int height(Node node) {
if (node == null) {
return 0;
}
int lHeight = height(node.left);
int rHeight = height(node.right);
if (Math.abs(lHeight - rHeight) > 1) {
throw new NotBalanced();
}
return Math.max(lHeight, rHeight) + 1;
}
|
或者用Integer.MIN_VALUE作为一异常值：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public int height(Node node) {
if (node == null) {
return 0;
}
int lHeight = height(node.left);
if (lHeight == Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
int rHeight = height(node.right);
if (rHeight == Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
if (Math.abs(lHeight - rHeight) > 1) {
throw Integer.MIN_VALUE;
}
return Math.max(lHeight, rHeight) + 1;
}
public boolean checkBalanced(Node root) {
return height(root) != Integer.MIN_VALUE;
}
|
评论