难度: Easy
给定一个二叉树，判断它是否是 平衡二叉树
示例 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
Submission
运行时间: 68 ms
内存: 19.6 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
if root is None:
return True
def get_height(root):
if root is None:
return 0
return max(get_height(root.left), get_height(root.right)) + 1
return abs(get_height(root.left) - get_height(root.right)) <= 1 \
and self.isBalanced(root.left) and self.isBalanced(root.right)
Explain
这个题解使用了递归的方法来判断二叉树是否平衡。对于每个节点，先递归计算其左右子树的高度，然后判断左右子树的高度差是否不超过1。如果高度差超过1，则说明以当前节点为根的子树不平衡，返回False。同时还要递归判断左右子树是否平衡。只有当前节点平衡且左右子树都平衡时，才说明以当前节点为根的子树是平衡的，返回True。
时间复杂度: O(n^2)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
if root is None:
return True
def get_height(root):
if root is None:
return 0
# 递归计算左右子树的高度
return max(get_height(root.left), get_height(root.right)) + 1
# 判断当前节点左右子树高度差是否不超过1，且左右子树都平衡
return abs(get_height(root.left) - get_height(root.right)) <= 1 \
and self.isBalanced(root.left) and self.isBalanced(root.right)
Explore
在本题解中，每次计算节点的平衡性时都重新计算高度，这确实导致了不必要的重复计算，增加了时间复杂度。使用一个辅助数据结构（如哈希表）来存储每个节点的高度可以避免重复计算，提高效率。不过，该题解可能是为了说明概念或简化实现。在实际应用或面试中，推荐使用带有缓存的方式来优化性能。
在极端不平衡的情况下，如完全倾斜的树（所有节点只有左子节点或只有右子节点），递归深度将与树的高度相同，即等于节点数。这种情况下，递归深度可以非常大，导致大量的栈空间使用，甚至可能引发栈溢出错误。因此，这种深度递归的方法在实际应用中可能会影响算法的性能和稳定性。
使用`max`函数是为了获取当前节点的最大高度，这是计算节点高度所必需的。然而，单单一个子树的不平衡并不会导致整个树不平衡，除非该不平衡子树影响了其上级节点。题解中同时检查节点两侧子树的高度差（不超过1）以及每个子树自身的平衡性。因此，整个树的平衡性是通过递归地检查所有节点的平衡性来确定的。
在二叉树的高度定义中，一个空树（null节点）的高度是0。这是因为高度通常定义为从节点到其最远子节点的边的最大数目，对于空树，没有节点，因此边的数目为0。这个定义是递归计算树高度的基础，有助于简化边界情况的处理。