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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param pRoot TreeNode类 
 * @return bool布尔型
 */
 //获得树的深度的函数
int getDepth(struct TreeNode* Root){
    if(Root==NULL){
        return 0;
    }
    int depth;
    int ldepth=getDepth(Root->left);
    int rdepth=getDepth(Root->right);
    depth=ldepth>rdepth?ldepth+1:rdepth+1;
    return depth;
}

bool IsBalanced_Solution(struct TreeNode* pRoot ) {
    // write code here
    //空树返回1
    if(pRoot==NULL){
        return 1;
    }
    //判断以当前结点为根的树是不是平衡树
    int leftdepth=getDepth(pRoot->left);
    int rightdepth=getDepth(pRoot->right);
    int diff=leftdepth-rightdepth;
    if(abs(diff)>1){
        return 0;
    }
    //递归判断每个结点
    return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
}