面试题55（二）：平衡二叉树

从“根看起来不歪”开始

先预测：一棵树的根左右子树深度相同，是否就一定平衡？不一定。某个子树内部仍可能是一条长链，根处差值为0，却有更深节点的左右深度差超过1。

作者定义的平衡二叉树要求任意节点左右子树深度差不超过1。某节点左深度减右深度称为平衡因子；所有节点都满足阈值才是平衡二叉树。

完全二叉树一定平衡，但平衡树不一定完全。作者Test2故意构造有空缺的树，最长左右深度只差1，期望true；它防止实现把“每层是否填满”误当成平衡条件。

方案一：在每个节点重新求深度

作者先复用上一题TreeDepth。对当前节点分别求左右深度，差值超界就返回false；当前节点通过后，再递归检查左右孩子。

int TreeDepth(
    const BinaryTreeNode* pRoot) {
    if (pRoot == nullptr) {
        return 0;
    }
    int nLeft =
        TreeDepth(pRoot->m_pLeft);
    int nRight =
        TreeDepth(pRoot->m_pRight);
    return nLeft > nRight
        ? nLeft + 1
        : nRight + 1;
}
 
bool IsBalanced_Solution1(
    const BinaryTreeNode* pRoot) {
    if (pRoot == nullptr) {
        return true;
    }
 
    int left =
        TreeDepth(pRoot->m_pLeft);
    int right =
        TreeDepth(pRoot->m_pRight);
    int diff = left - right;
    if (diff > 1 || diff < -1) {
        return false;
    }
 
    return IsBalanced_Solution1(
               pRoot->m_pLeft) &&
           IsBalanced_Solution1(
               pRoot->m_pRight);
}

这版逻辑直观，直接对应定义，也能正确短路：当前节点失衡时不检查孩子；左子树返回false时，逻辑与不会再检查右子树。

问题是深度计算和后续平衡检查相互独立。同一子树可能先被祖先的TreeDepth遍历，又在自己的节点上再次求孩子深度。一般可用O(nh)描述其重复工作上界，朴素最坏上界可到O(n平方)；平衡满树也会出现跨层重复，常见代价O(n log n)。

精确耗时受短路位置影响：纯长链在根处很快发现巨大差值，未必触发最坏重复；但不能据此把方案一宣传成稳定O(n)。作者给出它是为了从定义出发，再引出不重复访问的方案二。

方案二：一次返回状态和深度

判断当前节点是否平衡，需要先知道左右子树是否平衡以及各自深度。这天然对应。

作者让布尔返回值表示平衡状态，并通过int指针把子树深度写给调用方。这个第二输出称为。

bool IsBalanced(
    const BinaryTreeNode* pRoot,
    int* pDepth);
 
bool IsBalanced_Solution2(
    const BinaryTreeNode* pRoot) {
    int depth = 0;
    return IsBalanced(pRoot, &depth);
}
 
bool IsBalanced(
    const BinaryTreeNode* pRoot,
    int* pDepth) {
    if (pRoot == nullptr) {
        *pDepth = 0;
        return true;
    }
 
    int left;
    int right;
    if (IsBalanced(
            pRoot->m_pLeft, &left) &&
        IsBalanced(
            pRoot->m_pRight, &right)) {
        int diff = left - right;
        if (diff <= 1 && diff >= -1) {
            *pDepth =
                1 + (left > right
                    ? left
                    : right);
            return true;
        }
    }
    return false;
}

空树同时返回true并写深度0。非空节点只有在左右子树都平衡、当前差值也合法时，才写自身深度并返回true。

图中的Test2树先从叶节点返回，再由5、2、3汇总到根1。每个节点的深度就在平衡检查那一次计算中产生，不再另启TreeDepth遍历。

false路径为何不需要写深度

逻辑与从左到右短路。左子树失衡时，右子树不会执行；任一孩子失衡或当前差值超界时，函数返回false，但可能没有给当前pDepth写值。

这在作者调用链中安全：父层只有在子调用返回true时才读取对应left或right；外层IsBalanced_Solution2只返回布尔值，也不读取失败时的depth。

pDepth本身也必须非空。公开包装始终传入局部变量地址，递归也传入left和right地址，因此作者没有检查nullptr。若把核心函数暴露为公共API，应改用引用、结构化返回值，或检查指针。

作者固定先检查左子树。左侧失败后，逻辑与会跳过右侧，因此在左右两边都失衡时，实际首先发现的是左侧反例；把调用顺序交换后，最终布尔结果不变，但访问节点数和首个诊断位置可能不同。若函数只承诺true或false，这种差异不可观察；若扩展为返回“第一个失衡节点”，就必须规定前序优先级或返回全部反例，测试也不能只比较布尔值。

取消信号和访问预算也适合沿失败通道传播，但不应与“结构失衡”共用同一个false而丢失原因。工程版可返回枚举状态：平衡、失衡、输入损坏、资源超限，再附带有效深度。这样调用方能区分树本身不平衡和本次检查未完成，避免把超时误报成业务结论。

负一哨兵是等价改写

旧页只有“高度为-1表示失衡”的写法。它是方案二的常见现代化改写，但不是作者源码中的函数签名。合法深度从0开始，所以-1可作为不冲突的失败哨兵。

#include <algorithm>
#include <cstdlib>
 
int BalancedHeight(
    const BinaryTreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
 
    const int left =
        BalancedHeight(root->m_pLeft);
    if (left == -1) {
        return -1;
    }
 
    const int right =
        BalancedHeight(root->m_pRight);
    if (right == -1) {
        return -1;
    }
 
    if (std::abs(left - right) > 1) {
        return -1;
    }
    return std::max(left, right) + 1;
}
 
bool IsBalancedSentinel(
    const BinaryTreeNode* root) {
    return BalancedHeight(root) != -1;
}

布尔加出参与单一哨兵返回值都在做。前者类型含义更明确，后者代码更紧凑；若合法值域可能包含-1，则应改用结构体或optional，不能硬套哨兵。

也可以返回结构体，其中包含balanced与depth两个字段。这样即使未来要附带首个失衡节点、左右深度或诊断信息，也不会依赖魔法数字。

诊断结构还可以记录反例节点的左右深度。父层收到失败后应原样上送最深处或最先发现的反例，而不是用祖先覆盖它；否则日志只显示根不平衡，却看不到真正跨过阈值的位置。若需要所有失衡节点，就不能在第一次false时短路，时间仍是O(n)，但会遍历完整棵树并收集结果，语义和作者的快速布尔判断不同。

正确性：局部条件如何推出全树

对空树，函数返回平衡和深度0，符合定义。假设左右子树返回值正确：若任一子树不平衡，整棵当前树必然不平衡，失败传播正确；若两边都平衡，只需检查当前根的深度差。

差值在负1到1时，当前节点也局部平衡，且自身深度为较大子树深度加1；否则当前节点本身就是反例，应返回false。由结构归纳，根返回true当且仅当每个节点都满足条件。

优化版的每个节点只在一次后序调用中处理。短路可能让某些未访问分支更少，但不会让任何节点被重复处理，因此时间O(n)上界，递归栈空间O(h)。

完全、满、搜索与平衡是不同属性

平衡只约束左右子树深度差。它不要求节点值有序，因此普通二叉树也能判断平衡；不需要二叉搜索树性质。

完全二叉树要求除最后一层外都填满，最后一层从左连续；满二叉树常指每个节点孩子数为0或2，或每层都满，具体术语还需确认。它们都不是本题判断条件。

一棵只缺少某些叶位置的树可以平衡，一棵二叉搜索树也可能退化为长链而不平衡。平衡属性描述形状，不自动说明它采用AVL旋转、红黑规则或其他自平衡维护机制。

空树被定义为平衡，单节点也平衡。平衡判定期间树必须有限无环；带环指针会导致递归无法到达基例。

两套方案的工作量对照

方案一适合先验证定义和快速写出正确答案；方案二把“深度”和“平衡”合并到一个子树摘要中，是树形动态规划的典型模式。父节点只依赖孩子摘要，不需要重新扫描孩子内部。

若同一棵可变树要频繁查询平衡状态，可以在节点维护高度，并在插入删除后沿祖先更新；AVL树就是把高度差约束与旋转维护结合起来。作者题目只做一次离线判断，不修改树，也不要求修复失衡。

并发修改会让一次遍历混合不同版本结构。const指针仅防止当前函数写节点，不提供线程同步；生产接口应在不可变快照、读锁或单线程所有权下运行。

作者7组测试与14次核对

Test函数对每棵树先运行Solution1，再运行Solution2，因此7个场景共14次结果核对：

1. 7节点完全二叉树，期望true。
2. 非完全但每个节点差值不超过1，期望true。
3. 普通树中根或内部节点深度差为2，期望false。
4. 5节点纯左链，期望false。
5. 5节点纯右链，期望false。
6. 单节点树，期望true。
7. 空树，期望true。

左右单链成对出现，防止实现只正确处理一个差值符号；Test2防止把完全性误当平衡；空树和单节点锁定递归基例。

#include <cassert>
 
void assertBothSolutions(
    const BinaryTreeNode* root,
    bool expected) {
    assert(IsBalanced_Solution1(root)
           == expected);
    assert(IsBalanced_Solution2(root)
           == expected);
    assert(IsBalancedSentinel(root)
           == expected);
}
 
void testBalancedTrees(
    const BinaryTreeNode* complete,
    const BinaryTreeNode* irregular,
    const BinaryTreeNode* unbalanced,
    const BinaryTreeNode* leftChain,
    const BinaryTreeNode* rightChain,
    const BinaryTreeNode* single) {
    assertBothSolutions(complete, true);
    assertBothSolutions(irregular, true);
    assertBothSolutions(unbalanced, false);
    assertBothSolutions(leftChain, false);
    assertBothSolutions(rightChain, false);
    assertBothSolutions(single, true);
    assertBothSolutions(nullptr, true);
}

随机对拍可生成有限无环树，用作者两版和哨兵版比较布尔结果。还可用独立参考函数先为每个节点计算深度，再枚举检查所有差值，作为不共享实现细节的判定器。

性质测试包括：左右镜像不改变平衡结果；给叶节点增加一个孩子不会立即破坏该叶平衡，但可能让祖先跨过阈值；完全树删除最右侧某个叶子后仍可能平衡。

本章练习

概念说明

本章核心概念包括：每个节点只遍历一次。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

1. 平衡二叉树要求任意节点左右子树深度差不超过1。
2. 只检查根不够，每棵子树也必须平衡。
3. 作者方案一在每个节点重新求深度，正确但有重复遍历。
4. 方案二通过后序遍历同时返回布尔状态和深度出参。
5. 优化版让每个节点只遍历一次，时间O(n)、栈空间O(h)。
6. false路径通过短路向上传播，调用方不能再读取未承诺的深度。
7. -1高度哨兵是等价改写，不是作者原函数签名。
8. 作者7组场景对两套方案各检查一次，共14次核对。

名词解释