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 left and right subtrees of every node differ in height by no more than 1.
Example 1:
Given the following tree [3,9,20,null,null,15,7]:
3
/ \
9 20
/ \
15 7
Return true.
Example 2:
Given the following tree [1,2,2,3,3,null,null,4,4]:
1
/ \
2 2
/ \
3 3
/ \
4 4
Return false.
判断一棵二叉树是否是平衡二叉树。平衡二叉树是指任意子树的左右孩子高度差不超过1。 我最初的想法是DFS找到整棵树的最小和最大高度，然后判断这两个高度差是否超过1，但提交了好几次都只能通过部分样例，好忧伤。 后来看参考网上一个人的题解，还是很厉害的。网上题解都大同小异，思想就是算每棵子树的左右孩子高度差，但是有人是自顶向下的，有人是自底向上的，这里面复杂度当然有差别，如果自顶向下的算，那么很多子树的高度重复计算了，所以采用自底向上的方法比较好，求父亲的高度时，可以用到孩子的高度。 完整代码如下：
class Solution {
public:
int depth(TreeNode* root)
{
if (root == NULL)
return 0;
int left = depth(root->left); // 先不断递归到叶子
int right = depth(root->right);
if (left < 0 || right < 0)
return -1;
if (abs(left – right) > 1)
return -1;
return max(left, right) + 1; // 父亲高度利用了孩子的高度
}
bool isBalanced(TreeNode* root) { return depth(root) != -1; }
};本代码提交AC，用时13MS。
二刷。自己写的代码，子函数同时算高度和判断是否平衡，如下：
class Solution {
private:
bool isBalanced(TreeNode* root, int& height)
{
if (root == NULL) {
height = 0;
return true;
}
int lheight = 0, rheight = 0;
bool lbalanced = isBalanced(root->left, lheight);
bool rbalanced = isBalanced(root->right, rheight);
height = max(lheight, rheight) + 1;
bool balanced = abs(lheight – rheight) <= 1;
return lbalanced && rbalanced && balanced;
}
public:
bool isBalanced(TreeNode* root)
{
int height = 0;
return isBalanced(root, height);
}
};本代码提交AC，用时9MS。