力扣每日一题110：平衡二叉树

题目

简单

给定一个二叉树，判断它是否是 

平衡二叉树

  

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

• 树中的节点数在范围 [0, 5000] 内
• -104 <= Node.val <= 104

---

面试中遇到过这道题?

1/5

是

否

通过次数

608.6K

提交次数

1M

通过率

58.4%

方法一：自顶向下的递归

二叉树是平衡二叉树的三个条件

1、左子树与右子树的高度差<=1

2、左子树是平衡二叉树

3、右子树是平衡二叉树

class Solution {
public:
    int height(TreeNode *root)
    {
        if(root==NULL) return 0;
        return max(height(root->left),height(root->right))+1;
    }
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        return abs(height(root->left)-height(root->right))<=1&&isBalanced(root->left)&&isBalanced(root->right);
    }
};

时间复杂度：O()

空间复杂度：O(n)

方法二：自底向上的递归

方法一由于是自顶向下递归，因此对于同一个节点，函数 height 会被重复调用，导致时间复杂度较高。如果使用自底向上的做法，则对于每个节点，函数 height 只会被调用一次。

自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 −1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。

官方题解

class Solution {
public:
    int height(TreeNode* root,bool &balanced) {
        if (root == NULL) {
            return 0;
        }
        int leftheight=height(root->left,balanced);
        int rightheight=height(root->right,balanced);
        if(abs(leftheight-rightheight)>1||!balanced){
            balanced=false;
            return -1;
        }
        return max(leftheight,rightheight)+1;
    }

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

时间复杂度：O(n)

空间复杂度：O(n)