题目描述

输入二叉树的根节点,判断该树是不是平衡二叉树

样例

输入：二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示，
5
/ \
7 11
/ \
12 9

输出：true

算法

递归

可以结合二叉树深度的方法,递归判断每一个结点的左右子树是否都满足深度相差小于1的条件

C++ 代码

 class Solution {
 public:
    #计算树的深度
    int treeDepth(TreeNode* root){
        if(!root) return 0;
        return max(treeDepth(root->left),treeDepth(root->right))+1;
    }
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        int left = treeDepth(root->left);
        int right = treeDepth(root->right);
        #判断左右子树是否满足条件,然后如果满足条件,判断子树的子树是否满足条件
        if(abs(left-right)<=1) return isBalanced(root->left)&&isBalanced(root->right);

        #如果不满足条件直接返回false
        else return false;
    }
};