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 [3,9,20,null,null,15,7]:
Return true.
Example 2:
Given the following tree [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 是错误的，必须保证每一个节点都满足该条件。
解法思路
初始思路：
按照高度平衡二叉树的定义，可以想到通过遍历每一个节点，然后求每个节点的左右子树的高度，最后比较左右子树的高度差是否大于 1，当高度差大于时则返回 false，否则返回 true。实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int getHeight(TreeNode* root) {
if (root == NULL)
return 0;
else
return 1 + max(getHeight(root->left), getHeight(root->right));
}
bool isBalanced(TreeNode* root) {
if (root == NULL)
return true;
int left = getHeight(root->left);
int right = getHeight(root->right);
return abs(left - right) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}
};
|
复杂度分析：求个节点的高度调用 getHeight() 花费的时间复杂度是 O(N)，遍历所有节点又需要 O(N)，因此总的时间复杂度是 O(N^2)。
改进思路：
对于上面的方法，是从根往下，在求每一个节点的高度时都会遍历其子节点，这些操作有很多时重复的。如果可以每个节点的高度都保存下来就好了。对于这个题目，节点的值是没有用的，因此可以用节点的值来存放其高度，这样就没有额外的空间消耗。
代码如下：
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
| class Solution {
public:
void storeHeight(TreeNode* root) {
if (root == NULL)
return ;
storeHeight(root->left);
storeHeight(root->right);
if (root->left != NULL && root->right != NULL)
root->val = 1 + max(root->left->val, root->right->val);
else if (root->left != NULL)
root->val = 1 + root->left->val;
else if (root->right != NULL)
root->val =1+root->right->val;
else
root->val = 1;
}
bool helper(TreeNode* root) {
if (root == NULL)
return true;
int left = root->left == NULL? 0 : root->left->val;
int right = root->right == NULL? 0 : root->right->val;
return abs(left - right) <= 1 && helper(root->left) && helper(root->right);
}
bool isBalanced(TreeNode* root) {
storeHeight(root);
return helper(root);
}
};
|
复杂度分析：算法首先求出二叉树各节点的高度，时间复杂度为 O(N)；然后再递归的计算每个节点左右子树的高度差是否小于等于 1，时间复杂度也为 O(N)。所以总的时间复杂度为 O(N) + O(N) = O(N)。
最终解法：
在递归的计算二叉树中每个节点的高度时，如果两个子树的高度相差小于等于 1，则记录该节点真实的高度值，否则记录为 -1；并且在递归求某节点的高度时判断其左右孩子的高度值是否记录的是 -1，如果是，说明其左右子树中有非平衡树，则将该节点的高度值记为 -1。最后判断根节点的高度值是否为 -1，若为 -1，说明该二叉树不是高度平衡的；若不为 -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
| class Solution {
public:
int dfsHeight(TreeNode* root){
if (root == NULL) return 0;
int left = dfsHeight(root->left);
if (left == -1) return -1;
int right = dfsHeight(root->right);
if (right == -1) return -1;
if (abs(left - right) > 1) return -1;
return 1 + max(left, right);
}
bool isBalanced(TreeNode* root) {
if (dfsHeight(root) == -1)
return false;
else
return true;
}
};
|
复杂度分析：只需要遍历一遍所有节点即可，时间复杂度为 O(N)。