面试题28：对称的二叉树

从“左右孩子值相等够不够”开始

先预测：根1的左右孩子都为2；左侧2只有右孩子3，右侧2也只有右孩子3。两侧值序列看起来相同，这棵树对称吗？不对称。左侧的内侧右孩子应该对应右侧的内侧左孩子，而那里为空。

对称的二叉树要求沿根轴折叠后，结构和节点值都重合。每次比较的不是同一父节点下两个随意孩子，而是对称位置。

左半树按根、左、右访问，右半树按根、右、左访问；作者甚至直接让两个指针都从root开始，以这两种方向同步遍历整棵树。原书要点就是“前序遍历与对称前序遍历”的结果连同空位置完全一致。

对称前序不是简单倒序

的递归方向与普通前序相反。对一对节点p、q，下一层必须同时比较左-右与右-左：

1. p.left 与 q.right 是两棵半树的外侧配对。
2. p.right 与 q.left 是两棵半树的内侧配对。

把第一组称为，第二组称为。两组都成功，当前节点对才对称。

普通前序值序列再整体反转并不能替代对称前序。根位置、层级和空分支会丢失，重复值尤其容易让错误序列相等。正确方法在遍历过程中直接维持节点对关系。

空节点是结构的一部分

作者边界按顺序处理：p与q都为空返回true；仅一个为空返回false；两者值不同返回false；其余情况递归两组交叉孩子。只有先判断空，才能安全读取value。

空树调用isSymmetrical(root, root)，也就是比较null与null，因此返回true。单节点先比较根值，再递归两组null/null，也返回true。这符合“空结构和单点都关于自身轴对称”的定义。

把遍历中明确保留的空孩子位置称为。原书概念“空节点必须参与比较”不是要求真的构造空节点对象，而是控制流必须区分双空和单空。

忠实实现作者root与root递归

作者外层不是传root.left与root.right，而是把同一个root传给两个参数。第一层值必相等，下一层才形成root.left/root.right；这个写法让空树自然走双空成功。

struct BinaryTreeNode {
    int value;
    BinaryTreeNode* left = nullptr;
    BinaryTreeNode* right = nullptr;
};
 
bool isSymmetrical(BinaryTreeNode* first,
                   BinaryTreeNode* second) {
    if (first == nullptr && second == nullptr) {
        return true;
    }
    if (first == nullptr || second == nullptr) {
        return false;
    }
    if (first->value != second->value) {
        return false;
    }
 
    return isSymmetrical(first->left, second->right) &&
           isSymmetrical(first->right, second->left);
}
 
bool isSymmetrical(BinaryTreeNode* root) {
    return isSymmetrical(root, root);
}

也可直接返回isMirror(root->left, root->right)，空root先返回true。两种入口等价；忠实阅读源码时应知道作者利用了同根首层，而不是误以为函数在比较两棵独立输入树。

逻辑与具有短路行为：外侧失败后不再比较内侧，值或结构冲突能尽早返回。最坏仍访问每个节点常数次，时间O(n)；递归调用栈O(h)，斜树h=n。

迭代版必须成对保存节点

作者只提供递归版。工程迭代可以用队列保存节点对，每次取出一对，执行同样的双空、单空、值差判断，再按外侧和内侧成对加入：

#include <queue>
#include <utility>
 
bool isSymmetricalIterative(BinaryTreeNode* root) {
    using Pair =
        std::pair<BinaryTreeNode*, BinaryTreeNode*>;
    std::queue<Pair> pending;
    pending.push({root, root});
 
    while (!pending.empty()) {
        auto [first, second] = pending.front();
        pending.pop();
 
        if (first == nullptr && second == nullptr) {
            continue;
        }
        if (first == nullptr || second == nullptr ||
            first->value != second->value) {
            return false;
        }
 
        pending.push({first->left, second->right});
        pending.push({first->right, second->left});
    }
    return true;
}

使用pair比把单个节点依次压入队列更不容易打乱奇偶数量。队列中允许null，只在取出后按对解释；若容器API不接受null，可以存可选指针或在入队前直接比较空状态。

迭代时间O(n)，辅助空间与待比较节点对数量相关，最坏O(n)。用栈代替队列仍正确，变成深度优先；关键是每次弹出和压入都保持镜像配对。

全值相同为什么仍可能不对称

作者Test9和Test10所有节点值都是5。Test9左右分支向外镜像偏斜，结果true；Test10某一侧的最后节点方向改成同向，结果false。任何只看value的算法在两组输入上得到相同信息。

结构序列化可用“值、左、右”并写入空标记，然后比较普通前序与对称前序序列。递归双指针其实是在不显式构造两个序列的情况下在线比较，能在首次冲突处停止，空间也只需遍历状态。

若节点值本身重复或全部相同，地址不需要相等：镜像两侧本来就是不同节点。应比较业务值相等和结构对应，不能要求first==second；只有作者入口第一层同根地址相同。

与“镜像一棵树再比较”方法的关系

可以复制root的镜像，再判断原树与镜像副本结构和值相等；逻辑正确，但需要O(n)新节点和一次额外比较。若原地镜像后比较，原树已被修改，无法再同时作为对照，除非先复制或镜像两次恢复。

直接双指针对读输入，不分配节点，也不修改树，是更合适的判定。它与上一题镜像变换共享交叉方向规则，但一个是只读比较，一个是写入交换，副作用契约不同。

若树含父指针，判定只沿left/right，不应比较parent，否则左右两侧父地址天然不同。若业务要求比较其他字段，应注入等价谓词并保持镜像位置规则不变。

作者十组测试如何逐层加压

Test1是完整对称树；Test2只改第二层右值6为9，验证浅层值冲突；Test3删掉一个最外侧5，验证结构冲突。Test4构造四层镜像斜树，要求深层true；Test5把对应2改成6，深层值false；Test6缺少一侧最深节点，深层结构false。

Test7单节点true，Test8空树true。Test9和Test10所有值都为5，分别验证镜像偏斜true与同向偏斜false。这十组组合同时锁定值、结构、深度和空边界。

自动测试可构造核心六类并让递归与迭代交叉校验：

#include <cassert>
 
void testSymmetrical() {
    BinaryTreeNode n5a{5}, n7a{7}, n7b{7}, n5b{5};
    BinaryTreeNode n6a{6, &n5a, &n7a};
    BinaryTreeNode n6b{6, &n7b, &n5b};
    BinaryTreeNode n8{8, &n6a, &n6b};
 
    assert(isSymmetrical(&n8));
    assert(isSymmetricalIterative(&n8));
 
    n6b.value = 9;
    assert(!isSymmetrical(&n8));
    n6b.value = 6;
 
    n6b.right = nullptr;
    assert(!isSymmetrical(&n8));
    n6b.right = &n5b;
 
    BinaryTreeNode only{1};
    assert(isSymmetrical(&only));
    assert(isSymmetrical(nullptr));
 
    BinaryTreeNode a3{5}, b3{5};
    BinaryTreeNode a2{5, &a3, nullptr};
    BinaryTreeNode b2{5, &b3, nullptr};
    BinaryTreeNode root{5, &a2, &b2};
    assert(!isSymmetrical(&root));
}

最后一组两侧都向左，所有值相同，专门验证空位置。完整移植时还应保留作者Test4到Test6的深链，防止实现只检查固定层数。

属性测试可生成随机树T，构造独立镜像M，再把新根的左右分别接T和M，结果必对称；随机删除M中一个非对称位置，结果通常应false。删除前要确保不是删除一对同时为空的位置。

输入契约与工程边界

算法假设有限无环二叉树。孩子指针成环会无限递归；共享DAG节点可能被多个镜像路径重复比较，仍可能得到真假，但时间分析和“树”语义改变。容器应保证每个非根节点唯一父节点。

并发只读安全取决于节点生命周期和是否有写线程。若另一线程镜像或删除子树，比较可能看到混合结构或悬空地址；需读锁、不可变树或快照。

对极深树应使用显式栈/队列，避免调用栈溢出。迭代容器也要设置资源上限，恶意超宽树可能占用大量内存；流式处理无法在不保存对应镜像边界的情况下完全避免状态。

泛型节点应把“值相等”抽成等价谓词。若value是浮点数，NaN与容差策略要先定义；若是业务对象，可能只比较ID，也可能要求版本和状态都相同。结构对称与字段等价是两条独立条件，不能因为对象地址不同就判失败，也不能因为主键相同就忽略方向。

批量查询可为子树计算结构摘要，但普通摘要通常区分left与right；判断镜像时需要比较左摘要与右侧的镜像摘要。可为每个节点同时缓存正向摘要和镜像摘要，根的正向摘要等于镜像摘要时再做逐节点确认。哈希只能快速筛选，碰撞时仍不能替代精确比较。

若树节点带parent指针，镜像判定通常不沿parent，否则递归会回到祖先形成环；parent也不应要求两侧地址相等。遍历边集合必须限定为left和right，输入契约与比较字段都应显式写出。

正确性证明

对镜像节点对所覆盖的节点数归纳。双空表示两侧结构同时结束，正确；单空或值不同必不对称。两者非空同值时，整对对称当且仅当外侧子对与内侧子对都对称，递归恰好检查这两个必要且充分条件。

入口比较root与root。根值自然相同，下一层转为root.left与root.right；空root走双空true。由递归对子对的正确性，最终返回值与整棵树是否沿根轴对称完全一致。

本章练习

概念说明

本章核心概念包括：同时比较左-右与右-左。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

1. 对称的二叉树要求结构和值沿根轴同时镜像。
2. 前序遍历与对称前序遍历按根左右和根右左同步进行。
3. 每层同时比较左-右与右-左两组镜像节点对。
4. 双空成功、单空失败，空节点必须参与比较。
5. 作者入口比较root与root，因此空树和单节点都返回true。
6. 全部节点值相同也可能因空位方向不同而不对称。
7. 递归时间O(n)、栈O(h)，迭代队列最坏O(n)空间。
8. 十组官方测试覆盖浅深值差、结构差、空树和同值陷阱。

名词解释