题目描述
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
题解
两种思路：自底向上和自顶向下。自底向上计算，每个子树的高度只会计算一次。可以递归先计算当前节点的子节点高度，然后再通过子节点高度判断当前节点是否平衡，从而消除冗余。首先判断子树是否平衡，然后比较子树高度判断父节点是否平衡。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| bool f1(TreeNode* root, int& height){
if (!root) {
height = 0;
return true;
}
int left, right;
if (f1(root->left, left) && f1(root->right, right) && abs(left - right) < 2)
{
height = max(left, right) + 1;
return true;
}
return false;
}
bool isBalanced(TreeNode* root) {
if (!root)return true;
int h;
return f1(root, h);
}
|
通过函数参数取出计算的结果。