CS-Notes 剑指 Offer 55.2 详解：平衡二叉树的判定与自底向上后序遍历解法

本文基于 CS-Notes 仓库中 [剑指 Offer 55.2 平衡二叉树题解](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/55.2 平衡二叉树.md?utm_source=gitcode_repo_files) 展开，围绕“判断一棵二叉树是否为平衡二叉树”这一经典面试问题，完整讲解平衡树的定义、自顶向下与自底向上两种解法的复杂度差异、原题 O(n) 解法的逐行实现与提前剪枝原理，并串联仓库内的二叉树深度、Leetcode 110 等相关题解。读完后你可以独立推导树高类问题的最优递归写法，理解全局标记变量加提前终止的设计意图，并了解它在多线程场景下的替代方案。

1. 题目描述与平衡二叉树的定义

原题给出的定义只有一句话：平衡二叉树左右子树高度差不超过 1。这句话的严谨含义是：对树中的每一个节点，其左子树高度与右子树高度之差的绝对值都不超过 1。满足该性质的二叉树也称为高度平衡二叉树（AVL 树即在此基础上增加了插入删除时通过旋转维持平衡的操作）。

用文字画出 Leetcode 题解 - 树 中给出的判定示例：

        3
       / \
      9  20
        /  \
       15   7

• 节点 9：左右子树高度差 |0 - 0| = 0，平衡；
• 节点 20：左右子树高度差 |1 - 1| = 0，平衡；
• 根节点 3：左子树高度 1，右子树高度 2，高度差 |1 - 2| = 1，不超过 1，整棵树平衡。

如果把节点 15 换成一条更长的链（例如 20 下方接 3 层节点），右子树高度变成 4，根节点高度差为 3，判定结果即为 false。可见判定必须发生在每个节点上，而不能只看根节点。

2. 前置知识：树的深度

判断平衡的前提是求子树高度。仓库中 55.1 二叉树的深度 给出了标准后序递归写法：

public int TreeDepth(TreeNode root) {
    return root == null ? 0 : 1 + Math.max(TreeDepth(root.left), TreeDepth(root.right));
}

它的结构就是后续 55.2 解法中 height() 函数的骨架：空节点高度为 0，否则高度等于左右子树高度的较大值加 1。55.2 实际上是在这个骨架里“顺路”检查了每个节点的高度差，因此两道题应放在一起复习。

3. 朴素解法：自顶向下重复计算高度

最直观的思路是对每个节点分别求左右子树深度再比较：

public boolean isBalanced(TreeNode root) {
    if (root == null)
        return true;
    int leftDepth = TreeDepth(root.left);
    int rightDepth = TreeDepth(root.right);
    return Math.abs(leftDepth - rightDepth) <= 1
        && isBalanced(root.left)
        && isBalanced(root.right);
}

正确，但效率差：TreeDepth 在判断父节点时已经算过子树高度，递归到子节点时又重新计算了一遍。对于 n 个节点的左斜链（每个节点只有左孩子），自顶向下方案需要 O(n) + (n-1) + (n-2) + ... 次高度计算，最坏时间复杂度为 O(n²)；且即使发现最底层某节点已经失衡，上层递归仍会照常遍历完整棵树，无法提前结束。

4. 原题解法：自底向上后序遍历 + 全局标记

原题解 采用的是后序遍历（自底向上）一次遍历同时完成“求高度”与“判平衡”两件事：

private boolean isBalanced = true;

public boolean IsBalanced_Solution(TreeNode root) {
    height(root);
    return isBalanced;
}

private int height(TreeNode root) {
    if (root == null || !isBalanced)
        return 0;
    int left = height(root.left);
    int right = height(root.right);
    if (Math.abs(left - right) > 1)
        isBalanced = false;
    return 1 + Math.max(left, right);
}

逐行拆解其设计：

代码	作用
private boolean isBalanced = true;	全局标记，初始假定整棵树平衡，遍历中一旦发现问题节点即置为 false。牛客/剑指 Offer 的判题器是单线程单例调用，这种写法可以直接通过
if (root == null || !isBalanced) return 0;	两个终止条件：一是空节点高度为 0；二是一旦已确认失衡，立即剪枝，后续递归全部返回 0 快速退出，避免无谓遍历
int left = height(root.left); int right = height(root.right);	先递归左右子树（后序），拿到子树真实高度
if (Math.abs(left - right) > 1) isBalanced = false;	当前节点失衡，打上标记。注意此处不立即 return，高度仍需正常返回，供上层继续计算
return 1 + Math.max(left, right);	当前子树高度 = 较高子树高度 + 1，与 55.1 的 TreeDepth 完全同构

复杂度分析：

• 时间复杂度 O(n)：每个节点最多访问一次；!isBalanced 剪枝只会在失衡时让访问次数更少，不会更多。
• 空间复杂度 O(h)：h 为树高，是递归调用栈深度，平衡树为 O(log n)，最坏退化为链状时 O(n)。

这里的关键思想是：把“判断”寄生在“求高度”的回溯过程里。后序遍历保证了到达某个节点时其左右子树高度已经确定，一次递归同时回答两个问题；而自顶向下方案里高度需要被反复重算，这正是两者复杂度差的根源。

5. 改进写法：避免全局变量

原题用成员变量 isBalanced 传递结论，简单直接，但有两个工程隐患：一是判题器之外多次调用同一实例时状态会残留（第二次调用前需手动重置）；二是该对象若被多线程共享，存在竞态。可以改为用返回值同时携带“高度与结论”——约定失衡时返回 -1：

public boolean isBalanced(TreeNode root) {
    return check(root) != -1;
}

// 返回子树高度；失衡时返回 -1
private int check(TreeNode root) {
    if (root == null)
        return 0;
    int left = check(root.left);
    if (left == -1)
        return -1;              // 左子树已失衡，直接剪枝
    int right = check(root.right);
    if (right == -1)
        return -1;
    if (Math.abs(left - right) > 1)
        return -1;
    return 1 + Math.max(left, right);
}

两种写法时间、空间复杂度相同，后者无共享可变状态，在面试白板之外的实际代码中更常用。

6. 仓库内相关题解

同属“树高/后序遍历”问题族的仓库文档，建议按下面的顺序交叉复习：

• 55.1 二叉树的深度：height() 函数的原型，先掌握“后序求高度”这一基本功；
• Leetcode 题解 - 树：其中“2. 平衡树”一节用 maxDepth + 全局 result 标记解决了 Leetcode 110 (Balanced Binary Tree)，与本篇 55.2 是同一模式的两个版本，对比阅读可以看到同一思路在两套题面上的映射；
• 68. 树中两个节点的最低公共祖先：普通二叉树版 LCA 同样是“后序遍历 + 子树结论合并”的结构，其 return left == null ? right : right == null ? left : root; 一行合并左右子树结论的写法，与本题合并左右子树高度的思想一致；
• 剑指 Offer 题解 - 目录：完整的剑指 Offer 题解索引，“树”分类下包含本篇及上述所有题目。

7. 小结与面试要点

1. 定义要答全：平衡二叉树要求每个节点的左右子树高度差都不超过 1，只检查根节点是错误答案的典型来源；
2. 首选自底向上：后序遍历中顺便记录高度，每个节点只访问一次，O(n) 时间；自顶向下重复求高度的写法最坏 O(n²)，面试中可作为对比方案引出；
3. 剪枝与状态传递：原题通过 !isBalanced 提前终止递归，确认失衡后不再深入无关节点；用返回值（-1 表示失衡）代替全局布尔可以避免状态残留与线程安全问题；
4. 同族问题：树深度（55.1）、两节点最长路径、直径等题都复用“后序回溯返回高度”的骨架，掌握本篇解法后可直接迁移。