给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
2
3
4
5
6
7
| 1
/ \
2 2
/ \
3 3
/ \
4 4
|
返回 false 。
一颗树是平衡二叉树，当且仅当所有子树都是二叉平衡树，我们可以使用递归的方式来判断二叉树是否为平衡二叉树。
我们使用 height 函数来求树的最大高度，如果左右子树的高度不超过 1 ，再分别递归地遍历左右子节点，并判断左右子树是否为平衡二叉树。这是一个自顶向下的过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}else{
return Math.abs(length(root.left) - length(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
}
public int length(TreeNode root){
if(root == null){
return 0;
}else{
return Math.max(length(root.left), length(root.right)) + 1;
}
}
}
|
时间复杂度O(n^2)，最坏情况下，二叉树为链表，遍历所有结点时间复杂度O(n)，计算高度时间复杂度为O(n)。
空间复杂度O(n)。
我们可以递归地判断当前结点的左右子树是否平衡，再判断以当前结点为根的树是否平衡，如果平衡，返回其高度（不小于 0 ），否则返回 - 1，代表不是平衡二叉树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public boolean isBalanced(TreeNode root) {
return length(root) >= 0;
}
public int length(TreeNode root){
if(root == null){
return 0;
}
int leftLength = length(root.left);
int rightLength = length(root.right);
if(leftLength == -1 || rightLength == -1 || Math.abs(leftLength - rightLength) > 1){
return -1;
}else{
return Math.max(leftLength, rightLength) + 1;
}
}
}
|
时间复杂度O(n)，空间复杂度O(n)。