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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return bool布尔型
     */
    bool IsBalanced = true;
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(!pRoot) return true;
        depth(pRoot);   
        return IsBalanced;
    }

private:
    int depth(TreeNode* pRoot){
        if (!pRoot) return 0;
        int left = depth(pRoot->left);
        int right = depth(pRoot->right);
        if (abs(left-right)>1) {
            IsBalanced = false;
        }
        return 1+max(left,right);
    }
};
//在求深度的过程加了一个if判断是否平衡,即使发现不平衡,递归仍会继续

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        return checkBalance(pRoot) != -1;
    }

private:
    int checkBalance(TreeNode* root) {
        if (!root) return 0;
        
        int left = checkBalance(root->left);
        if (left == -1) return -1;
        
        int right = checkBalance(root->right);
        if (right == -1) return -1;
        
        if (abs(left - right) > 1) return -1;
        
        return 1 + max(left, right);
    }
};

/*if (left == -1) return -1; 的作用：
如果左子树已经不平衡，跳过右子树的递归计算
直接向上层返回不平衡状态
if (right == -1) return -1; 的作用：
如果右子树已经不平衡，跳过当前节点的平衡性检查
直接向上层返回不平衡状
*/