LeetCode 剑指 Offer 55 - II. 平衡二叉树

约 10 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 字节跳动 剑指 Offer 剑指 Offer（第 2 版）
标签
深度优先搜索 树 二叉树
目录

题目描述

✅ 剑指 Offer 55 - II. 平衡二叉树

image-20241107211959475

题意分析

判断一棵二叉树是不是「高度平衡」的。题目给的定义很具体：树中每一个节点的左右两棵子树的高度差的绝对值都不超过 1。

这里最关键的是「每一个节点」这四个字。它不是只要求根节点的左右子树高度接近，而是对树里的所有节点都提出了同样的要求。只要有任意一个节点违反，整棵树就不平衡。所以判断本身是一个遍历所有节点并逐个校验的过程。

反过来看，这个定义又是递归可分解的：整棵树平衡，当且仅当根节点自身满足高度差条件，且左子树平衡、右子树也平衡。三个条件缺一不可，这个分解直接决定了算法的骨架。

每个节点的校验需要知道它左右子树的高度，而高度本身也是一个递归量：height(node) = max(height(left), height(right)) + 1，空节点高度为 0。于是「校验」和「求高度」这两件事天然纠缠在一起——这正是本题真正的考点：如何在一次遍历里同时把两个信息带上来。

节点数上限是 5000，$O(n)$ 完全够用，但 $O(n^2)$ 在退化成链的树上是 2500 万次操作，虽然勉强能过判题，却是面试里会被追问的写法。

边界：空树按定义平衡，返回真；单节点树左右子树高度都是 0，差为 0，平衡。这两种都应该自然落进递归基。

解法：后序剪枝

核心思路

最直白的写法是照抄定义：写一个 height 函数求高度，再写 isBalanced(root) 判断「根的左右高度差不超过 1 且左子树平衡且右子树平衡」，两个函数互相调用。

它的瓶颈很明显：同一棵子树的高度被反复计算。判断根节点时算了一次整棵左子树的高度，递归去判断左子树时又把它下面的高度全部重算一遍。对退化成链的树，总复杂度是 $O(n^2)$。

突破口是观察遍历的方向。求高度是自底向上的：必须先知道孩子的高度，才能算出自己的高度。而平衡性的校验恰好也可以在这个时刻顺便完成——当我们拿到左右子树高度的那一刻，正好就能判断当前节点是否满足高度差条件。既然两件事发生在同一个时间点，就没有理由分两趟做。

问题变成：一个递归函数怎么同时返回「高度」和「是否平衡」两个值？可以定义一个小结构体或返回数组，但更简洁的做法是用一个哨兵值把两个信息编码进同一个整数：正常情况返回真实高度（非负），一旦发现不平衡就返回 -1。因为真实高度永远不可能是负数，-1 不会与任何合法高度混淆，这个编码是无歧义的。

于是 height(node) 的语义变成：若以 node 为根的子树平衡，返回它的高度；否则返回 -1。这个双重语义必须在写代码前就明确下来，否则分支很容易写乱。

递归的处理顺序是标准的后序：先算左子树，如果它返回 -1 就立刻把 -1 继续往上抛（剪枝，不必再算右子树）；再算右子树，同样处理；两边都正常时才比较高度差，超过 1 则返回 -1；否则返回 max(left, right) + 1。

这个剪枝是复杂度从 $O(n^2)$ 降到 $O(n)$ 的关键：每个节点的高度只被计算一次，且一旦发现不平衡就中止后续所有计算。

主函数只需判断 height(root) != -1。空树时 height 返回 0，不等于 -1，正确地判为平衡。

解题步骤

  • 主函数写成 return height(root) != -1：把布尔结论从哨兵编码里解出来。空树会走 height 的递归基返回 0，自然被判为平衡，不需要在主函数里特判。
  • 递归基：node == null 返回 0：空子树高度为 0，且它必然平衡。这个返回值同时承担了「高度」和「平衡」两层含义，与函数的双重语义一致。
  • 先递归左子树，拿到 left 后立刻检查是否为 -1，是则直接返回 -1：这一步是剪枝的核心。左边已经不平衡，整棵树的结论就定了，右子树连算都不用算。把检查紧跟在递归调用之后，而不是等两边都算完再一起判，能省掉最坏情况下一半的计算。
  • 再递归右子树，同样立刻检查：逻辑对称。注意两次检查必须分别紧跟各自的递归调用。
  • 比较 Math.abs(left - right) > 1 则返回 -1：走到这里说明两棵子树各自都平衡，只剩当前节点这一处需要校验。用绝对值是因为哪边高都算违规；Go 的实现里写成 left-right > 1 || right-left > 1，效果等价且省掉了函数调用。
  • 最后返回 Math.max(left, right) + 1：当前节点平衡，返回它的真实高度。加 1 是算上当前节点自己这一层。
  • 全程不需要任何全局变量：每一层的返回值就携带了该层子问题的完整结论，逐层向上汇总即可。

以 [3,9,20,null,null,15,7] 走一遍（平衡，应返回 true）。这棵树的根是 3，左孩子 9 是叶子，右孩子 20 有两个叶子孩子 15 和 7。

height(3) 先递归左边：height(9) 再递归它的两个空孩子，各返回 0；|0-0| = 0 不超过 1，返回 max(0,0)+1 = 1。left = 1，不是 -1，继续。

height(3) 递归右边：height(20) 先算 height(15)，它的两个空孩子返回 0，故 height(15) = 1；再算 height(7) = 1；|1-1| = 0，返回 max(1,1)+1 = 2。right = 2，不是 -1，继续。

回到 height(3)：|1 - 2| = 1，不超过 1，返回 max(1,2)+1 = 3。

主函数得到 3，不等于 -1，返回 true，正确。

再看反例 [1,2,2,3,3,null,null,4,4]：根 1 的左子树是以 2 为根、下面挂着两个 3、其中左边那个 3 又挂着两个 4；根 1 的右孩子是叶子 2。

height(1) 递归左边到 height(左2)：先算 height(左3)——它的两个孩子 4 各返回 1，|1-1| = 0，返回 2；再算 height(右3) = 1；|2 - 1| = 1 不超过 1，返回 max(2,1)+1 = 3。所以 left = 3。

接着算右边 height(右2) = 1，right = 1。

回到 height(1)：|3 - 1| = 2 > 1，返回 -1。主函数判 -1 != -1 为假，返回 false，正确。

体会一下剪枝的作用：如果不平衡发生在更深的位置，比如某个孙子节点处返回了 -1，那么它的父节点在 left == -1 这一行就立刻返回，兄弟子树的整个递归都被跳过；而朴素的两函数写法会把每棵子树的高度重新算一遍。

代码实现

class Solution {
    // 当前节点若左右高度差超过 1，也返回 -1。
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }

    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left = height(node.left);
        if (left == -1) {
            return -1;
        }

        int right = height(node.right);
        if (right == -1) {
            return -1;
        }

        if (Math.abs(left - right) > 1) {
            return -1;
        }

        return Math.max(left, right) + 1;
    }
}

func isBalanced(root *TreeNode) bool {
    // 当前节点若左右高度差超过 1，也返回 -1。
    return height(root) != -1
}

func height(node *TreeNode) int {
    if node == nil {
        return 0
    }

    left := height(node.Left)
    if left == -1 {
        return -1
    }

    right := height(node.Right)
    if right == -1 {
        return -1
    }

    if left-right > 1 || right-left > 1 {
        return -1
    }

    if left > right {
        return left + 1
    }
    return right + 1
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是节点数。每个节点的高度只在它自己那一层被计算一次，计算本身是常数次比较与加法；一旦某处返回 -1，剩余子树会被整段跳过，实际访问量只会更少。这正是它优于朴素双函数写法 $O(n^2)$ 的地方。
  • 空间复杂度：$O(h)$，其中 $h$ 是树高，来自递归栈。树平衡时是 $O(\log n)$——恰好是本题返回真的那些输入；树退化成链时是 $O(n)$，而这类输入通常会在浅层就返回 -1 提前收工。算法不使用任何额外数据结构。

关键点总结

  • 一个递归要同时向上传递多个信息时，先想能不能用哨兵值编码。这里真实高度恒非负，所以 -1 可以安全地表示「不平衡」；选哨兵的唯一标准是它绝不可能与合法返回值重合。相比开结构体或返回数组，这个技巧代码最短，是面试白板上的首选。
  • 明确写出递归函数的双重语义（「平衡则返回高度，否则返回 -1」）再动手写分支，是不写乱的前提；面试时把这句话说出来，比逐行念代码更能体现设计意识。
  • 「求高度」和「校验平衡」发生在同一时刻，所以应该在一趟后序遍历里同时完成。凡是发现某个量被重复计算，就该问「能不能自底向上一次带上来」——这是把树形递归从 $O(n^2)$ 优化到 $O(n)$ 的通用手法。
  • 剪枝要紧跟在每个递归调用之后，而不是等所有子调用都返回再统一判断；前者能在左子树失败时省掉整棵右子树的计算。
  • 注意题目定义的是「每一个节点」而非只看根节点；读清这个量词才能得到正确的递归分解，这是本题最容易在读题阶段就跑偏的地方。

易错点总结

  • 只检查根节点的左右高度差：[1,2,2,3,3,null,null,4,4] 的根左右高度差是 2 会被抓到，但换成 [1,2,3,4,null,null,null,5] 这类深层才失衡的树，根的高度差可能不超过 1，会误判为 true。
  • 写成 height 和 isBalanced 互相调用的两函数版本：逻辑正确但高度被反复计算，退化成链的 5000 节点树需要约 2500 万次操作，面试中会被要求优化到一趟。
  • 发现不平衡后返回 0 而不是 -1：0 是空树的合法高度，父节点无法区分「子树是空的」和「子树不平衡」，[1,null,2,null,3] 会被误判为平衡。
  • 递归基返回 -1（把空树高度当成 -1）：这与不平衡的哨兵值撞车，任何含空孩子的节点都会立刻判定不平衡，所有非满二叉树都返回 false。
  • 拿到 left 后不立刻检查就去算 right：结果仍正确，但丢掉了剪枝，最坏情况下白算一整棵子树。
  • 比较高度差时忘记取绝对值：写成 left - right > 1，[1,null,2,null,3] 这类只往右深的树会漏判，返回错误的 true。
  • 主函数写成 return height(root) > 0：空树的 height 返回 0，会被判为不平衡，而空树按定义是平衡的。
  • 返回高度时忘记加 1：Math.max(left, right) 少算了当前层，所有节点的高度恒为 0，任何树都被判为平衡。
  • 用 left + right + 1 当高度：那是节点数或路径长度的算法，[3,9,20,null,null,15,7] 会算出错误的高度并连带判错平衡性。
  • 用一个全局布尔变量记录结果却在递归里写成赋值而非取与：后续分支的 true 会覆盖前面已经发现的 false，[1,2,2,3,3,null,null,4,4] 可能返回 true。
  • 误以为「平衡二叉树」等价于「完全二叉树」：[1,2,3,4,null,null,7] 不是完全二叉树但完全平衡；两个概念毫无关系。

相似题目

题目 难度 考察点
110. 平衡二叉树 简单 与本题同题，可直接套用
面试题 04.04. 检查平衡性 简单 与 110 同题
104. 二叉树的最大深度 简单 只求高度不做校验，是本题递归函数去掉哨兵后的裸形态
剑指 Offer 55 - I. 二叉树的深度 简单 与 104 同题
111. 二叉树的最小深度 简单 求最浅叶子的深度，单侧为空时不能直接取 min，需特判
559. N 叉树的最大深度 简单 孩子数量不定，需遍历 children 取最大值
543. 二叉树的直径 简单 同为后序带高度上传，但答案是全局最优，需用成员变量在递归中更新
687. 最长同值路径 中等 在 543 基础上加值相等的约束，孩子值不同时贡献要归零
124. 二叉树中的最大路径和 困难 返回值是「向上贡献」而答案是「跨节点最优」，两者语义必须严格区分
108. 将有序数组转换为二叉搜索树 简单 反过来构造一棵平衡树，每次取中点作根即可保证高度差不超过 1
1382. 将二叉搜索树变平衡 中等 先中序遍历成有序数组，再套 108 的构造法重建