题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

思路

平衡二叉树：对于任何一棵子树，左右子树的高度相差不超过1
对于任何一个节点满足条件：左右子树的高度相差不超过1
跟左右子树要信息：高度

下面求高度
对于任何一个节点的高度：左右子树的最大深度+1
跟左右子树要信息：深度

代码

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(pRoot==NULL)
            return true;
        if(Depth(pRoot->left)-Depth(pRoot->right)<2&&Depth(pRoot->left)-Depth(pRoot->right)>-2)
            return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);
        else
            return false;
    }
    int Depth(TreeNode* pRoot)
    {
        if(pRoot==NULL)
            return 0;
        return max(Depth(pRoot->left),Depth(pRoot->right))+1;
    }
};