题解 | #判断是不是平衡二叉树#

class Solution {
public:
    int ult=0,max=0;
    void dep(TreeNode* root,int h){        //计算某子树的深度
        if(h>max) max=h;
        if(root->left!=NULL) dep(root->left,h+1);
        if(root->right!=NULL) dep(root->right,h+1);
    }

    void cmpis(TreeNode* root){           //判断某节点是否平衡
        int ldep=0,rdep=0;
        if(root->left!=NULL) {        //ldep记录左子树高度
            dep(root->left,1);
            ldep=max;
            max=0;
        }
        else ldep=0;
        if(root->right!=NULL){         //rdep记录右子树高度
            dep(root->right,1);
            rdep=max;
            max=0;
        }
        else rdep=0;
        int jieguo=ldep-rdep;
        if(jieguo>1||jieguo<-1) ult=1;     //若某节点不平衡，ult置1，该树不平衡
    }

    void panduan(TreeNode* root){        //判断每个结点的平衡情况
        cmpis(root);
        if(root->left!=NULL) panduan(root->left);
        if(root->right!=NULL) panduan(root->right);
    }

    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(pRoot==NULL) return true;
        panduan(pRoot);
        if(ult==1) return false;
        else return true;
    }
};