110. 平衡二叉树

自上而下递归：

代码语言：javascript复制

class Solution {
public:
    bool isBalanced(TreeNode* root) 
    {
        if(root==NULL)
        return true;
        //平衡条件：左右子树高度差小于1，并且左右子树都是平衡树
        return abs(getHigh(root->left)-getHigh(root->right))<=1&&isBalanced(root->left)&&isBalanced(root->right);
    }
    //计算二叉树高度的函数
    int getHigh(TreeNode* root)
    {
        return root==NULL?0:max(getHigh(root->left),getHigh(root->right)) 1;
    }
};

自下而上的递归：

代码语言：javascript复制

class Solution {
public:
    int height(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        int leftHeight = height(root->left);
        int rightHeight = height(root->right);
        //发现一个子树不平衡，那么整棵树就不可能平衡
        if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return max(leftHeight, rightHeight)   1;
        }
    }

    bool isBalanced(TreeNode* root) {
        return height(root) >= 0;
    }
};

递归

0 人点赞