面试题27：二叉树的镜像

从“交换根够不够”开始

先预测：根8的左子树以6为根、右子树以10为根。只交换根的left和right，能得到完整镜像吗？不能。两棵子树整体换边后，它们内部每个节点的左右关系也必须翻转。

的局部规则非常统一：空节点无操作，非空节点交换left与right，再对两个孩子执行同一规则。节点value、地址和父子层级不变，只有左右方向反转。

原书概念“二叉树的镜像”应落实为交换左右子节点，不是交换两个孩子的value。值相同的树即使交换value也看不出变化，而真实链接仍未镜像；测试必须检查节点地址与方向。

动手推导时应先做“画图分析”：把原树和镜像树放在同一层级，对每个节点画一条身份对应线，再检查原left是否成为镜像right、原right是否成为镜像left。先只画根能看出整体换边，再展开一层就会发现还必须继续递归处理子树；这比只写层序值更能暴露深层未交换的问题。

图中还要保留空孩子位置。原节点只有右孩子时，镜像后必须只有左孩子；若省略空位，左右斜树在纸面上都像一串相同数值，无法判断方向。带空标记的结构图、序列化和地址断言表达的是同一件事：镜像改变边的位置，不改变节点集合。

递归顺序怎样保证每个节点只交换一次

最直接的是：当前节点先完成局部镜像，随后处理新的左、右子树。后序也正确，可以先镜像两个原子树再交换根链接。

中序若机械写成“递归左、交换、递归右”会出错：交换后right已经是刚处理过的原left，于是它被处理第二次，原right却移到了left而被跳过。若一定使用中序风格，交换后应处理新的left，也就是原right；更清晰的选择仍是前序或后序。

所有正确遍历共有一个不变量：每个真实节点恰好执行一次left/right交换。访问次序可以是深度优先、广度优先或后序，只要不因交换后的字段变化重入同一子树。

作者仓库递归版有一个可复现缺陷

作者仓库当前提交的递归入口写成：节点为空，或者left为空且right为真时返回。第二部分实际表示“左空、右非空”，不是“左右都空的叶子”。因此右斜树在根处直接返回，完全没有镜像。

源码Test3正是右斜树，但测试只打印递归和迭代结果，没有断言。递归未改结构后，迭代再镜像一次，最终只看到一棵左斜树；若不分别断言两个实现，很容易漏掉缺陷。

修正后的递归实现

真正叶子条件应是left与right都为空。不过这项特判并非必需：只检查root为空，对叶子交换两个空指针后递归两次空节点，同样正确。下面保留叶子快速返回以直观对照源码：

#include <utility>
 
struct BinaryTreeNode {
    int value;
    BinaryTreeNode* left = nullptr;
    BinaryTreeNode* right = nullptr;
};
 
void mirrorRecursively(BinaryTreeNode* node) {
    if (node == nullptr ||
        (node->left == nullptr && node->right == nullptr)) {
        return;
    }
 
    std::swap(node->left, node->right);
    mirrorRecursively(node->left);
    mirrorRecursively(node->right);
}

这里执行。调用者持有的root地址不变，函数无需返回新头；但原树结构被破坏，其他共享读者会看到镜像后的链接。

先交换再递归时，node->left指向原right，node->right指向原left；两边都继续处理，所以覆盖完整。若写后序，必须先保存或直接递归原left、原right，再交换当前字段，覆盖也完整。

作者迭代版使用显式栈

作者第二种解法把root压入stack。每次弹出一个节点，交换左右指针，再把非空孩子压栈，直到栈空：

#include <stack>
#include <utility>
 
void mirrorIteratively(BinaryTreeNode* root) {
    if (root == nullptr) return;
 
    std::stack<BinaryTreeNode*> pending;
    pending.push(root);
 
    while (!pending.empty()) {
        BinaryTreeNode* node = pending.top();
        pending.pop();
 
        std::swap(node->left, node->right);
        if (node->left != nullptr) {
            pending.push(node->left);
        }
        if (node->right != nullptr) {
            pending.push(node->right);
        }
    }
}

这个版本不会因递归深度触发系统栈溢出。它仍需辅助空间：斜树通常栈中只有少量节点，宽而深的形状可能积累多个待处理分支，最坏O(n)。

也可用队列做BFS，空间O(最大层宽)。现有页面曾把BFS描述为作者迭代方案，但源码实际使用std::stack，是DFS。两者都正确，复刻时应把作者实现与工程变体分开。

镜像两次必须恢复原结构

同一节点左右交换两次会恢复原字段；树中每个节点都执行两次，所以mirror(mirror(T))=T。这种是非常强的测试关系。

但双镜像恢复不能单独证明第一次正确：什么都不做两次也会“恢复”。必须先断言第一次结果等于期望镜像，再执行第二次并断言所有原节点地址、left和right完全恢复。

原书Test1到Test3正好先调用递归、打印，再调用迭代、打印，意图上利用两次镜像恢复原树以便销毁。由于两个实现不同，第二次能恢复只在第一次确实镜像时成立；右斜树缺陷破坏了这个假设。

原地版本与拷贝版本

原地镜像时间O(n)，递归辅助空间O(h)，其中h为树高；显式栈或队列空间取决于待处理节点数。它不分配业务节点，适合调用方独占且允许修改的树。

若原树需要保留，可以创建新节点：新节点value复制原节点，新left递归复制原right，新right递归复制原left。时间O(n)、新节点空间O(n)，返回值拥有一棵独立镜像。

不可变树还可共享完全不变的叶子值对象，但链接节点仍要重新构造。若节点含父指针，原地交换孩子后父指针仍指向同一父节点，无需改变；若含缓存的左右摘要、路径编码或有序范围，必须同步重算。

二叉搜索树镜像后通常变成降序搜索树：左侧值大于根、右侧值小于根。结构镜像正确不等于仍满足原BST比较约定；依赖查找操作的调用方必须切换比较方向或不要原地镜像。

空树、叶子和斜树为何重要

空树验证入口不解引用root；单节点验证两个空孩子交换无害。左斜树要求每个左孩子变为右孩子，右斜树要求每个右孩子变为左孩子，二者共同防止条件只覆盖一侧。

完整树验证同一节点同时有两侧孩子时，子树整体换边且内部也递归。只有完整树和叶子仍不足以发现作者的“左空右非空”早退，因为完整树内部也可能没有这种形状。

结构测试应保存节点地址，而不仅是层序值。镜像前后层序值在重复值树上可能完全相同，但地址的左右关系应交换。序列化时带空标记也能精确表达形状。

作者五组测试与自动断言

Test1是7节点完整树8、6、10、5、7、9、11；Test2是8到4的纯左链；Test3是同值纯右链；Test4空树；Test5单节点。每组分别运行递归与迭代。

下面让两个实现各自在独立重建或已恢复结构上接受断言，避免互相掩盖：

#include <cassert>
 
void testMirror() {
    BinaryTreeNode n5{5}, n7{7}, n9{9}, n11{11};
    BinaryTreeNode n6{6, &n5, &n7};
    BinaryTreeNode n10{10, &n9, &n11};
    BinaryTreeNode n8{8, &n6, &n10};
 
    mirrorRecursively(&n8);
    assert(n8.left == &n10 && n8.right == &n6);
    assert(n10.left == &n11 && n10.right == &n9);
    assert(n6.left == &n7 && n6.right == &n5);
 
    mirrorIteratively(&n8);
    assert(n8.left == &n6 && n8.right == &n10);
 
    BinaryTreeNode r4{4}, r5{5, nullptr, &r4};
    BinaryTreeNode r6{6, nullptr, &r5};
    BinaryTreeNode r7{7, nullptr, &r6};
    BinaryTreeNode r8{8, nullptr, &r7};
    mirrorRecursively(&r8);
    assert(r8.left == &r7 && r8.right == nullptr);
 
    BinaryTreeNode only{1};
    mirrorIteratively(&only);
    assert(only.left == nullptr && only.right == nullptr);
    mirrorRecursively(nullptr);
}

右斜断言会直接抓住仓库递归条件缺陷。还可生成随机树，先序列化带空标记，镜像一次与参考拷贝比较，镜像第二次再与原序列化完全相等。

测试失败后销毁树时必须以当前结构为准；若结构错误成环，普通递归销毁可能无限递归。测试夹具用栈节点或在限定步数内先检查无环，可以隔离算法错误与清理崩溃。

并发、共享与异常边界

原地镜像不是原子操作。并发遍历者可能看到根已交换而子树尚未交换的混合结构；需要独占锁，或先构造镜像副本再原子发布新root。

若树是DAG而非独占树，同一共享子节点可能从两条路径被访问并交换两次，最终局部恢复而不是镜像。算法前提是每个非根节点只有一个父节点；共享结构需要已访问集合，或复制语义。

指针交换本身不会抛异常。拷贝镜像若分配失败，必须由unique_ptr等所有权类型自动清理已构造部分，才能提供强异常保证。裸new递归若中途抛出，会泄漏已创建子树。

正确性证明

对节点数归纳。空树和叶子显然正确。假设左右子树都能被递归正确镜像；当前节点先交换左右链接，再分别镜像交换后的两棵子树，于是原右子树成为完整镜像左树，原左子树成为完整镜像右树，整棵树正确。

显式栈版把同一局部操作应用于每个可达节点。每个节点只入栈一次、弹出一次并交换一次，最终链接结果与递归版相同。总时间O(n)，并因有限树和待处理集合不断耗尽而终止。

本章练习

本章回顾

1. 二叉树的镜像要求每个节点交换左右子节点。
2. 递归前序先交换当前，再递归处理交换后的两棵子树。
3. 作者迭代版使用显式栈做DFS，不是BFS队列。
4. 仓库递归叶子条件漏写right为空比较，右斜树会被错误跳过。
5. 修正条件为左右都为空，或只保留root为空的基础判断。
6. 原地镜像时间O(n)，递归空间O(h)，显式容器空间取决于树形。
7. 镜像具有对合性质，但测试仍要先断言第一次镜像正确。
8. 五组官方树形覆盖完整、左斜、右斜、空和单节点。

名词解释