判断平衡二叉树：从自顶向下到自底向上

本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。AVL 树的旋转在 408 选择题里年年出现，但「判断一棵给定的树是否平衡」这个更基础的操作，代码大题从没直接考过。它的暴力解到最优解的升级路径，和真题里「消除重复计算」是同一手段，值得单独练一遍。它是经典训练题，不是真题，也不押题。

题目

给定一棵二叉树的根结点，判断它是否为平衡二叉树——即树中每个结点的左右子树高度差的绝对值都不超过 1。要求分析时间复杂度。

这道题按拓展训练导语的分类，属于「暴力→最优」型——朴素解法能写对，但有真实的复杂度分差，值得走一遍完整的升级路径。

第一步：把暴力解写对——自顶向下逐结点检查

最直接的想法：对树中每一个结点，分别求出它左子树的高度和右子树的高度，看差值是否超过 1；然后对左右子树递归做同样的检查。

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 求以 root 为根的子树的高度
int height(TreeNode *root) {
    if (root == NULL) return 0;
    int lh = height(root->left);
    int rh = height(root->right);
    return (lh > rh ? lh : rh) + 1;
}

int isBalanced(TreeNode *root) {
    if (root == NULL) return 1;
    int lh = height(root->left);
    int rh = height(root->right);
    int diff = lh - rh;
    if (diff > 1 || diff < -1) return 0;
    return isBalanced(root->left) && isBalanced(root->right);
}

拿一棵简单的树走一遍：根 1，左孩子 2 挂着左孩子 4，右孩子 3。isBalanced(1) 先算 height(2)=2、height(3)=1，差值 1，不超标；接着递归检查 isBalanced(2)——它再算 height(4)=1、height(NULL)=0，差值 1，不超标；递归检查 isBalanced(4)，左右都是空树，直接判定平衡。整棵树判定为平衡二叉树。

复杂度：height() 本身是对一棵子树做一遍遍历，是 $O(\mathrm{该}\mathrm{子}\mathrm{树}\mathrm{的}\mathrm{结}\mathrm{点}\mathrm{数})$；isBalanced() 对树中的每一个结点都要触发一次 height() 调用。当树的结构不能在浅层就通过局部检查提前发现不平衡（也就是需要一路验证到底）时，越靠近根的结点触发的 height() 调用覆盖的子树越大，层层叠加，最坏情况下时间复杂度退化到 $O(n^2)$；只用了递归栈，空间 $O(h)$（h 为树高）。

它值多少分

拓展题按真题同样的两维度看（详见真题专题总纲）：

• 正确性：这份暴力解对每个结点都严格按定义（左右子树高度差 ≤ 1）做了判断，逻辑上一定正确，复杂度分析 $O(n^2)$ 与实现一致。正确性维度的分拿得到。
• 最优性：如果题面要求「尽可能高效」，期望是线性的 $O(n)$——毕竟判断平衡与否至少要把每个结点看一遍，$O(n)$ 是下界。$O(n^2)$ 的暴力解达不到，这一档拿不到。

也就是说，一份写对的自顶向下暴力解拿正确性分、丢最优性分。这道题的浪费藏在一个很容易被忽略的地方：高度信息被反复计算。

暴力解的浪费在哪

用总纲的「找浪费三问」审这份暴力解：

有没有重算已知的东西？——有，而且是这道题唯一的浪费来源。 关键在 isBalanced() 递归到子结点时的行为：检查完当前结点、确认它是平衡的之后，代码接着调用 isBalanced(root->left)。这次调用内部会再次计算 height(root->left->left) 和 height(root->left->right)——但左子树内部每个结点的高度信息，在上一层计算 height(root->left) 时其实已经被算过一次了（height() 内部本身就是递归地算出了左子树里每一层结点的高度，只是算完就丢掉，没有保存下来）。

举个具体的：一棵结构合理、层数较深的平衡树中，最底层附近的某个结点的子树高度，会在它的父结点、祖父结点、曾祖父结点……做各自的平衡检查时被反复求解。树越深，同一段子树的高度被重新计算的次数越多。

浪费的本质：height() 每次都从头对一整棵子树重新遍历求高度，而这个高度信息在更早的递归层级里其实已经算出来过，只是没有被保留、复用。

智慧化改造：自底向上一遍算完，顺带剪枝

对策是总纲里的第二类手段——把中间结果存下来，避免重算。这里不需要额外的存储结构，只需要调整递归的组织方式：把「求高度」和「判平衡」合并成同一次递归，让每个结点的高度在算出来的那一刻就顺便完成本结点的平衡判断，直接通过返回值向上传递，不再让父结点重新算一遍。

// 返回值：以 root 为根的子树高度；若子树本身或其某个子树已不平衡，返回 -1 作为哨兵
int checkHeight(TreeNode *root) {
    if (root == NULL) return 0;

    int lh = checkHeight(root->left);
    if (lh == -1) return -1;                 // 左子树已不平衡，直接向上传递、不再继续算

    int rh = checkHeight(root->right);
    if (rh == -1) return -1;                 // 右子树已不平衡，直接向上传递

    if (lh - rh > 1 || lh - rh < -1) return -1;   // 当前结点自己不平衡

    return (lh > rh ? lh : rh) + 1;           // 平衡：正常返回高度
}

int isBalanced(TreeNode *root) {
    return checkHeight(root) != -1;
}

从暴力解升级过来，几处最容易翻车：

• 用 -1 作哨兵值，把「高度」和「是否平衡」两件事塞进同一个返回值。正常情况下 checkHeight 返回的是真实高度（非负整数）；一旦发现不平衡，直接返回 -1，且这个 -1 会沿着递归调用链一路向上传递、每一层都直接放弃后续计算——这就是「提前终止」的具体做法。
• 左子树已经不平衡时,不必再去算右子树的高度。if (lh == -1) return -1; 这一行是关键的剪枝：一旦左子树已经判定不平衡，整棵树必然不平衡，右子树高度算不算都不影响最终结果，没必要再花时间遍历。
• 每个结点的高度只被计算一次。checkHeight 是唯一一个会递归遍历子树的函数，且对树中每个结点只调用一次——不存在父结点重新计算子结点子树高度的情况，浪费被彻底消除。
• AVL 树的实际实现更进一步：把高度缓存成结点的字段。这里演示的是"一次遍历里不重算"，而真正的 AVL 树结点（如 AVL 树详解 里的 AVLNode）直接给每个结点加一个 height 字段，插入、删除时增量更新，连"重新遍历子树算高度"这一步都省掉了——这是同一个思路在动态维护场景下的进一步延伸。

复杂度：每个结点只在 checkHeight 里被访问一次、做常数次操作（比较、返回），时间 $O(n)$；递归栈空间 $O(h)$。这就是把暴力解的重复计算彻底消除后的结果，也是判断平衡二叉树能达到的最优复杂度。

两版对照跑一遍

同一棵树（根 1，左孩子 2 挂着左孩子 4，右孩子 3）。先看自顶向下暴力解——注意每一层的平衡检查都会重新对下面的子树调用一次 height()：

加载可视化中...

再看自底向上最优解——每个结点的高度只算一次，checkHeight 顺带完成平衡判断,遇到不平衡立即用 -1 剪枝：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

等价方法与升级空间

• -1 哨兵是「提前终止」的通用手段，本质和 KMP 主串指针只进不退、2022·41 顺序存储判 BST 中序遍历时一发现逆序就能提前判断失败是同一类思路——一旦已经拿到能确定最终答案的信息，就不再对已经没有意义的部分继续计算。
• 动态维护场景下的进一步优化：缓存高度字段。这道题给的是一棵静态树，一次性判断是否平衡；而 AVL 树面对的是频繁插入删除的动态场景，如果每次插入后都重新对全树跑一遍这里的 $O(n)$ 判断，插入 n 个元素总代价会退化到 $O(n^2)$。AVL 树的做法是给每个结点缓存 height 字段，插入/删除时只需要沿着受影响的那条路径回溯更新，把单次维护代价降到 $O(\log n)$——这是本题「自底向上一遍算完」思路在增量场景下的自然延伸，详见AVL 树详解。

下一步

• 看平衡二叉树的旋转与结构演示：AVL 树可视化
• 同属「树与二叉树」的拓展题：二叉树的最大深度、判断对称二叉树
• 回到方法论源头：「暴力解到最优解」真题专题总纲