题目

简单

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

平衡二叉树

  

示例 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)