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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

/**
 * 
 * @param pRoot TreeNode类 
 * @return bool布尔型
 */
 //方法:双重递归问题（一个获得深度的递归函数，一个遍历判断是否为平衡二叉树的主函数），递归结束条件为空树
 //1、局部函数（获得深度的递归函数），跳出递归条件是：节点为NULL
    //（1）判空树，,返回0
    //(2)定义深度变量depth
    //(3)定义左右子树的深度lDepth,rDepth,并重复嵌套递归各自子树的深度
    //（4）三目运算符判断左右子树的高度，选择子树高的自增1，赋值给depth

 //2、主函数（遍历判断是否为平衡二叉树,递归结束的条件：空树和sub绝对值大于1 ）
    //（1）判空树，返回1（是二叉树）
    //(2)定义左右子树深度变量lDepth,rDepth，调用获得深度函数来各自赋值
    //（3）定义变量sub用于存储,深度变量lDepth和rDepth的差
    //(4)判断sub就绝对值abs大于1，返回0；否则进行下一步
    //(5)递归判断每一个节点



//1、局部函数（获得深度的递归函数），跳出递归条件是：节点为NULL
int getDepth(struct TreeNode *Root)
{
    //（1）判空树，,返回0
    if(!Root)
    {
        return 0;
    }

    //(2)定义深度变量depth
    int depth = 0;
    
    //(3)定义左右子树的深度lDepth,rDepth,并重复嵌套递归各自子树的深度
    int lDepth = getDepth(Root->left);
    int rDepth = getDepth(Root->right);

    //（4）三目运算符判断左右子树的高度，选择子树高的自增1，赋值给depth
    depth = lDepth>rDepth?lDepth+1:rDepth+1;
    return depth;
}
    
bool IsBalanced_Solution(struct TreeNode* pRoot ) 
{
    // write code here
    //主函数（遍历判断是否为平衡二叉树,递归结束的条件：空树和sub绝对值大于1 ）
    //（1）判空树，返回1（是二叉树）
    if(!pRoot)
    {
        return 1;
    }

    //(2)定义左右子树深度变量lDepth,rDepth，调用获得深度函数来各自赋值
    int lDepth = getDepth(pRoot->left);
    int rDepth = getDepth(pRoot->right);

    //（3）定义变量sub用于存储,深度变量lDepth和rDepth的差
    int sub = lDepth - rDepth;

    //(4)判断sub就绝对值abs大于1，返回0；否则进行下一步
    if(abs(sub)>1)
    {
        return 0;
    }

    //(5)递归判断每一个节点
    return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);

}