题目
给定一个二叉树，判断它是否是平衡二叉树。
- 示例 1：
输入：
root = [3,9,20,null,null,15,7]
输出：true
- 示例 2：
输入：
root = [1,2,2,3,3,null,null,4,4]
输出：false
- 示例 3：
输入：
root = []
输出：true
- 提示：
树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104
解法1：自顶向下由最大深度进行计算
- 平衡二叉树是指该树所有节点的左右子树的深度相差不超过 1
- 很容易联想到使用二叉树的最大深度计算方法，计算左右子树的深度差并判断，然后再计算子树的左右子树的深度差，再进行判断，不断递归
class Solution {
public:
int maxDepth(TreeNode* root){
if(!root) return 0;
return max(maxDepth(root->left), maxDepth(root->right))+1;
}
bool isBalanced(TreeNode* root) {
if(!root) return true;
return isBalanced(root->left) && isBalanced(root->right) && abs(maxDepth(root->left)-maxDepth(root->right)) <= 1;
}
};
解法2：剪枝——后序遍历
- 解法1 很容易想到，但是缺点是重复计算比较多，因为需要计算子树的高度差，子树的子树的高度差
- 如果从底至顶进行遍历，当发现左右子树高度差大于1 时，立刻返回，可减少不必要的重复操作
- 如果高度差符合要求，就返回当前的最大深度即可
class Solution {
public:
int postOrder_maxDepth(TreeNode* root){//后序遍历最大深度
if(!root) return 0;
int leftDepth = postOrder_maxDepth(root->left);
if(leftDepth == -1) return -1;
int rightDepth = postOrder_maxDepth(root->right);
if(rightDepth == -1) return -1;
return abs(leftDepth-rightDepth)<=1 ? max(leftDepth, rightDepth)+1 : -1;
}
bool isBalanced(TreeNode* root) {
return postOrder_maxDepth(root) != -1;
}
};