023 · Balanced Binary Tree

algorithm
Published

May 27, 2026

My First Thoughts

这道题第一眼看起来，是在复用 019 · Maximum Depth of Binary Tree。

因为题目问一棵树是不是高度平衡，而高度平衡的判断，本质上还是要看左右子树的最大深度。

所以可以先把 019 里的最大深度函数拿出来：

def maxDepth(root):
    if root is None:
        return 0

    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)

    return 1 + max(left_depth, right_depth)

接下来就要想：怎么用这个 maxDepth 来判断平衡？

最开始可能会想，比较 root 的左右节点最大深度是不是就行：

left_depth = maxDepth(root.left)
right_depth = maxDepth(root.right)

if abs(left_depth - right_depth) > 1:
    return False

但这马上会遇到第一个问题：只看 root 的左右高度差是不够的。

因为可能出现这种情况：从根节点看，左右两边差不多高；但是左子树内部某个节点的左分支一直往下走，右分支直接没了。这样根节点本身可能没问题，但下面的节点已经违背了平衡要求。

所以这道题不是只判断根节点，而是：

每个节点的左右分支最大深度差都需要在 1 以内。

因此对每个节点，都可以先做同样的事情：

left_depth = maxDepth(node.left)
right_depth = maxDepth(node.right)

if abs(left_depth - right_depth) > 1:
    return False

如果当前节点已经不平衡，那可以直接返回 False。

但如果当前节点平衡，也不一定能直接返回 True。因为这只说明当前节点没问题，不代表它的左子树和右子树内部也都没问题。

所以还需要继续往下判断：

isBalanced(node.left)
isBalanced(node.right)

这里真正容易卡住的是：这个“下一个节点”到底怎么表述？

它不是只去左节点，也不是只去右节点，而是左右两个方向都要判断。也就是说，当前节点通过高度差检查之后，还要继续确认：

左子树是平衡的
右子树也是平衡的

两个都成立，当前这棵树才算平衡。

所以返回值应该表达成：

return isBalanced(node.left) and isBalanced(node.right)

这里不是 !isBalanced(...)。Python 里逻辑取反写作 not，但这道题不需要取反。因为我们要的是“左边平衡并且右边平衡”，所以直接用：

isBalanced(node.left) and isBalanced(node.right)

如果有一边返回 False，整体就会返回 False。如果两边都返回 True，整体才返回 True。

再看边界。

如果 root is None，它本身没有节点，也就没有任何节点违反平衡条件，所以空树可以返回 True。

叶子节点也能自然处理：它的 left 和 right 都是 None，左右最大深度都是 0，高度差是 0，然后继续判断两个空子树，都会返回 True。

所以一个直观版本可以写成：

def isBalanced(root):
    def maxDepth(node):
        if node is None:
            return 0

        left_depth = maxDepth(node.left)
        right_depth = maxDepth(node.right)

        return 1 + max(left_depth, right_depth)

    if root is None:
        return True

    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)

    if abs(left_depth - right_depth) > 1:
        return False

    return isBalanced(root.left) and isBalanced(root.right)

这个版本的逻辑是对的。

它确实检查了每一个节点：当前节点先比较左右最大深度，如果当前节点没问题，再递归检查左子树和右子树。

Why That Is Not Enough

上面的解法已经可以通过逻辑判断，但它不是最优解。

问题在于：maxDepth 会被重复计算很多次。

例如在 isBalanced(root) 里，我们会计算：

maxDepth(root.left)
maxDepth(root.right)

然后递归到 isBalanced(root.left) 时，又会继续计算：

maxDepth(root.left.left)
maxDepth(root.left.right)

这些子树的高度，其实在前面算 maxDepth(root.left) 的时候已经算过一次了。

也就是说，直观解法是：

  1. 先用 maxDepth 扫一遍子树，得到高度
  2. 再进入子树，又重新扫里面的小子树
  3. 越靠上的节点，越容易造成重复计算

在一棵完全平衡的树里，这个重复也会很明显：

        1
       / \
      2   3
     / \ / \
    4  5 6  7

检查节点 1 时，maxDepth(root.left) 会扫过以 2 为根的整棵子树，maxDepth(root.right) 会扫过以 3 为根的整棵子树。

接着递归到节点 2 时，又会重新计算节点 4 和节点 5 下面的高度。

递归到节点 3 时，也会重新计算节点 6 和节点 7 下面的高度。

也就是说，同一批节点的高度信息会在不同层里被反复求。对一棵平衡树来说，这种写法通常会到 \(O(n \log n)\)；如果写成不提前停止、每个节点都完整检查的 top-down 版本，还可能更糟。

它相较于正解的不足，不是思路方向错了，而是：

判断平衡和计算高度分成了两套递归，导致高度被反复计算。

更好的做法是把这两件事合并在一次递归里完成。

Final Idea

直观解法的问题是重复计算高度。

那怎么减少重复呢？

先回到原来的 maxDepth：

def maxDepth(node):
    if node is None:
        return 0

    left_depth = maxDepth(node.left)
    right_depth = maxDepth(node.right)

    return 1 + max(left_depth, right_depth)

这个函数本来就在做一件事：

先拿到左子树高度，再拿到右子树高度，最后返回当前节点高度。

而判断平衡时，也正好需要这两个值：

abs(left_depth - right_depth) <= 1

所以可以把问题改成：

能不能在计算高度的时候，顺便判断这棵子树是不是平衡？

也就是说，不要在外面另外写一个 isBalanced，然后反复调用 maxDepth。

而是让“求高度”这个递归函数多做一步：

  1. 先求左子树高度
  2. 再求右子树高度
  3. 用这两个高度判断当前节点是否平衡
  4. 如果平衡，就返回当前高度
  5. 如果不平衡，就返回一个特殊信号

这里的问题是：函数本来应该返回高度，那如果发现不平衡，返回什么？

可以返回 -1。

因为正常高度不会是负数：

  • 空树高度是 0
  • 叶子节点高度是 1
  • 更高的树高度只会更大

所以 -1 可以专门表示：

这棵子树已经不平衡了，不用再把它当作正常高度处理。

这样，原来的 maxDepth 就变成一个更强的函数。它不只是求高度，而是：

如果子树平衡，返回它的高度；如果子树不平衡，返回 -1。

可以把它叫作 height(node)。

先处理空节点：

if node is None:
    return 0

然后像 maxDepth 一样，先去算左子树：

left_height = height(node.left)

但这里要多检查一步。

如果左子树返回的是 -1，说明左子树内部已经不平衡。既然左子树已经不平衡，那么当前这棵树也一定不平衡，所以可以直接继续返回 -1：

if left_height == -1:
    return -1

右子树也是一样：

right_height = height(node.right)
if right_height == -1:
    return -1

走到这里，说明左右子树本身都没有发现不平衡。现在才检查当前节点：

if abs(left_height - right_height) > 1:
    return -1

如果当前节点左右高度差超过 1，当前子树不平衡，返回 -1。

如果当前节点也平衡，那就和原来的 maxDepth 一样，返回真实高度：

return 1 + max(left_height, right_height)

这样一来，整棵树只需要从根节点调用一次：

return height(root) != -1

如果最后不是 -1，说明整棵树平衡；如果是 -1，说明某个位置已经发现不平衡。

这个写法的核心变化其实只有一句话：

把“先求高度，再判断平衡”合并成“求高度的过程中顺便判断平衡”。

Why It Works

高度平衡的定义要求每个节点都满足：

左子树平衡
右子树平衡
左右子树高度差不超过 1

height(node) 正好按这个顺序检查。

它先递归拿到左子树高度。如果左子树已经返回 -1，说明左子树内部有节点不平衡，当前树也不可能平衡。

右子树同理。

当左右子树都没有问题时，当前节点只需要比较：

abs(left_height - right_height)

如果高度差超过 1，返回 -1；否则返回当前子树的真实高度。

所以这个函数每次返回都有明确含义：

  • 返回 -1：这棵子树不平衡
  • 返回非负数：这棵子树平衡，并且这个数就是它的高度

主函数检查 height(root) != -1，就能得到整棵树是否平衡。

Code

def isBalanced(root):
    def height(node):
        if node is None:
            return 0

        left_height = height(node.left)
        if left_height == -1:
            return -1

        right_height = height(node.right)
        if right_height == -1:
            return -1

        if abs(left_height - right_height) > 1:
            return -1

        return 1 + max(left_height, right_height)

    return height(root) != -1

Complexity

Time \(O(n)\) - 每个节点最多被访问一次，同时完成高度计算和平衡判断
Space \(O(h)\) - 递归调用栈的深度等于树的高度 h，最坏情况下可以到 \(O(n)\)

Takeaway

这题的关键不是单独写一个函数去“判断平衡”，再单独写一个函数去“计算高度”，而是意识到计算高度的递归过程中已经拿到了判断平衡需要的信息。递归返回值不一定只能表示正常答案，也可以用特殊值传递失败状态：非负数表示子树高度，-1 表示这棵子树已经不平衡。

← Quiz