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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.08.04
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @brief 遍历二叉树,严格控制每一个结点的左右子树都是平衡二叉树
 *  (一)第一个左孩子，以其为根节点的树是否为平衡二叉树
 *  (二)第一个右孩子，以其为根节点的树是否为平衡二叉树
 *  (三)遍历每一个结点，并判断(一)、(二)
 * @param pRoot TreeNode类 
 * @return bool布尔型
 */
 //求树的高度
int maxDepth(struct TreeNode* root ) {
    // write code here
    if(root == NULL)
    {
        return 0;
    }

    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);

    return (leftDepth > rightDepth)?leftDepth + 1 : rightDepth + 1;
}

//当前结点是否为平衡二叉树
bool IsBalanced_Solution(struct TreeNode* pRoot ) {
    // write code here
    //空树必为平衡二叉树
    if(pRoot == NULL)
    {
        return true;
    }

    int leftDepth = maxDepth(pRoot->left);//左子树的高度
    int rightDepth = maxDepth(pRoot->right);//右子树的高度

    //高度差大于1则不是平衡二叉树
    if(abs(leftDepth - rightDepth) > 1)
    {
        return false;
    }    

    //左右子树都是平衡二叉树
    return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
}