05 August 2008
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.
Example 1:
Given the following tree 1
[3,9,20,null,null,15,7]
1
2
3
4
5
3
/ \
9 20
/ \
15 7
Return true.
Example 2:
Given the following tree 1
[1,2,2,3,3,null,null,4,4]
1
2
3
4
5
6
7
1
/ \
2 2
/ \
3 3
/ \
4 4
Return false.
平衡二叉树的定义：两个子树的高度相差不会超过1，而且左右子树都是平衡的。用动态规划的两个套路，自底向上和自顶向下来解。
利用递归，算出左右子树的深度，然后严格按照平衡二叉树的定义看左右子树的深度是否相差大于1。其中findDepth()的复杂度需要遍历每个结点为O(n)，而对所有结点都会执行以下findDepth()，所以总体时间复杂度为O(n^2)，空间为O(n)。
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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
//左右子树的深度
int left = findDepth(root.left);
int right = findDepth(root.right);
return Math.abs(left - right) <= 1 //随时检查
&& isBalanced(root.left) && isBalanced(root.right);
}
//递归找到子树的深度
private int findDepth(TreeNode node) {
if (node == null) {
return 0;
}
return Math.max(findDepth(node.left), findDepth(node.right)) + 1;//node不为0深度至少为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
33
34
35
36
37
38
39
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
HashMap<TreeNode, Integer> memo = new HashMap<>(); // 记忆化
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
int left = findDepth(root.left);
int right = findDepth(root.right);
return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int findDepth(TreeNode node) {
if (node == null) {
return 0;
}
if (memo.containsKey(node)) {
return memo.get(node);
}
int curDepth = 1 + Math.max(findDepth(node.left), findDepth(node.right));
memo.put(node, curDepth);
return curDepth;
}
}
也可以利用DFS，在DFS的递归中返回当前结点的height，如果当前结点的子结点是平衡的，dfsHeight()会返回一个非负整数，如果不平衡就返回-1，然后根据leftHeight和rightHeight的结果来决定一层层上升传递的数值。
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
33
34
35
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
return dfsHeight(root) != -1;//检查返回的数字决定是否平衡
}
private int dfsHeight(TreeNode root) {
if (root == null) {//递归的终止条件，查到最后还是平衡的就返回-1
return 0;
}
//回溯时层层传递
int leftHeight = dfsHeight(root.left);
if (leftHeight == -1) { // 提前返回
return -1;
}
int rightHeight = dfsHeight(root.right);
if (rightHeight == -1) { // 提前返回
return -1;
}
if (Math.abs(leftHeight - rightHeight) > 1) { // 提前返回
return -1;
}
return Math.max(leftHeight, rightHeight) + 1;//返回当前结点的height
}
}