题解 | #平衡二叉树#

核心思想是递归。首先写一个递归函数来返回树的高度，然后主函数中递归调用该函数比较左右子树的高度。
没有什么特别需要注意的点，就是时间复杂度和空间复杂度有点高。但是也没有想象的那么高。

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(!pRoot || (!pRoot->left && !pRoot->right)){
            return true;
        }
        if(!pRoot->left){
            if(getHeight(pRoot->right, 0) > 1){
                return false;
            }
            return IsBalanced_Solution(pRoot->right);
        }
        if(!pRoot->right){
            if(getHeight(pRoot->left, 0) > 1){
                return false;
            }
            return IsBalanced_Solution(pRoot->left);
        }
        if(abs(getHeight(pRoot->left, 0) - getHeight(pRoot->right, 0)) > 1){
            return false;
        }
        return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
    }
    int getHeight(TreeNode* p, int level){
        level++;
        if(!p->left && !p->right){
            return level;
        }
        else if(!p->left){
            return getHeight(p->right, level);
        }
        else if(!p->right){
            return getHeight(p->left,level);
        }
        else{
            if(getHeight(p->left,level) > getHeight(p->right, level)){
                return getHeight(p->left,level);
            }
            else{
                return getHeight(p->right,level);
            }
        }
    }
};