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

第二十一题 递归计算树高 并判断 是否是平衡二叉树

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(pRoot == NULL)
            return true;
        // 递归判断左右子树是不是平衡二叉树
        // 定义 左右子树的高度差 最大为1
        
        // 获得左右子树高度
        int l_height=get_height(pRoot->left);
        int r_height=get_height(pRoot->right);
        
//         cout<<l_height << r_height<<endl;
        // 如果高度为-1 就说明下面已经有不平衡的了，直接return false
        // 否则 判断左右子树高度是否相差 大于1
        if(l_height ==-1 || r_height ==-1 || abs(l_height - r_height) > 1)
            return false;
        else
            return true;
    }
    
    // 递归 计算高度 加上判断左右子树是否平衡
    // 如果不平衡 直接返回-1
    int get_height(TreeNode* root)
    {
        int height=0;
        // 递归结束条件 只有一个结点 高度为0
        if(root==NULL)
            return height;
        // 递归调用计算左右子树的高度 （包括 是否平衡的-1）
        int l_height=get_height(root->left);
        int r_height=get_height(root->right);
        
        // 如果说 有-1 则直接全部返回-1
        if(l_height==-1 || r_height==-1)
            return -1;
        // 如果 左右子树高度相差大于1，则返回-1
        // 这个判断 也就是上面所说的子树判断是否平衡、是否返回-1的问题
        if(abs(l_height - r_height) > 1)
            return -1;
        // 如果平衡 返回 高度最大的值+1 1就是当前这一层
        else
            return (l_height>r_height?l_height:r_height)+1;
    }
};