CS-Notes 剑指 Offer 题解：二叉树的镜像（第 27 题）—— 前序递归、迭代与非破坏式实现全解析

本篇指南基于 CS-Notes 仓库中《剑指 Offer 题解》树类专题的第 27 题 二叉树的镜像，系统讲解"镜像二叉树"这一经典递归问题的完整解法：从原题递归思路、逐节点交换的不变式，到时间/空间复杂度分析、防栈溢出的迭代版本与不修改原树的构造版本。读完本篇，你可以掌握二叉树"原地修改类"题目的标准分析方法，并能在面试白板中流畅写出递归、迭代两种等价实现并说明其边界条件与风险点。

一、题目描述

原题：输入一棵二叉树，输出其镜像树。

上图为题目给出的标准示例：左边一棵根节点为 1、左孩子 2、右孩子 3 的二叉树，其镜像树在右侧——根节点不变，两个子树的左右位置整体互换，得到根 1、左孩子 3、右孩子 2 的树。

这道题在《剑指 Offer》题解目录中归入树类专题，与 对称的二叉树 是同一张示例图、同一组递归思维的姊妹题：镜像题考察"自底向上地把左右子树位置交换到底"，对称题考察"两棵子树是否互为镜像"。完整的题目索引见 剑指 Offer 题解 - 目录。

注意本题的一个隐含要求：在原树结构上做原地（in-place）变换，而不是新建一棵树返回。这一约束直接决定了最简解法的形态。

二、核心思路：先交换当前节点，再递归处理子树

原文档给出的标准解法是前序遍历框架下的原地交换：

public TreeNode Mirror(TreeNode root) {
    if (root == null)
        return root;
    swap(root);
    Mirror(root.left);
    Mirror(root.right);
    return root;
}

private void swap(TreeNode root) {
    TreeNode t = root.left;
    root.left = root.right;
    root.right = t;
}

逐步拆解这段代码的正确性：

1. swap(root) 的作用：用临时变量 t 交换当前节点的 left 与 right 指针。交换是"纯指针操作"，不触碰节点内部数据（val 不变），因此不会破坏树中任何节点本身，只是改变了父子边的指向。
2. 交换先于递归：先对当前节点做 swap，再分别调用 Mirror(root.left) 与 Mirror(root.right)。此时 root.left、root.right 已经是交换后的子树，递归保证子树内部的所有节点最终也都完成左右互换。
3. 递归顺序的选择：这里是"先交换根、再递归子树"的框架，等价于以前序遍历的顺序访问节点。由于每一层的交换只影响当前层的左右指针、彼此独立，后序交换在结果上同样正确（交换操作可交换结合），但"先根后子"更贴近前序遍历的直觉，也是面试中最不易写错的顺序。
4. 递归终止条件：root == null 时直接返回，空指针既是叶子节点子指针的出口，也覆盖了整棵树为空树的输入。
5. 返回值：返回的是同一个 root 对象——结构已镜像，但节点身份未变，调用方持有的根引用依然有效。

用题目示例走一遍递归

以示例树 1(2, 3) 为例，调用栈展开如下：

步骤	动作	树的状态（括号内为左右孩子）
1	Mirror(1)，执行 swap(1)	1(3, 2)
2	递归 Mirror(3)，无孩子，swap 后返回	1(3, 2)
3	递归 Mirror(2)，无孩子，swap 后返回	1(3, 2)
4	返回根	镜像完成

若子树更复杂，比如根 1 下是左子树 4(5,6) 与右子树 7(8,null)，则 swap(1) 后两棵子树整体互换位置，随后 Mirror(4) 与 Mirror(7) 递归地使 4(6,5)、7(null,8)，最终整棵树逐节点镜像。这个"每层只交换一次指针、位置整体翻转"的过程正是镜像几何含义的直接实现。

三、复杂度与递归深度风险

设树中共有 n 个节点，树高为 h：

• 时间复杂度 O(n)：每个节点恰好被访问一次，每次 swap 是 O(1) 的指针操作，总代价线性。
• 空间复杂度 O(h)：递归调用栈深度等于树高。平衡树时 h = O(log n)；当树退化成链表形态（所有节点只有单侧孩子）时 h = O(n)。

这里有一个工程上必须指出的风险：在极端不平衡输入下，O(n) 深度的递归可能触发 StackOverflowError。这是"原地递归镜像"方案的固有边界，若题目数据规模不可控，应改用下文的迭代版本。

四、迭代版本：用显式栈替代递归

用栈模拟前序遍历，先交换当前节点再入栈子节点（入栈顺序不影响正确性，因为每个节点只被处理一次）：

import java.util.ArrayDeque;
import java.util.Deque;

public TreeNode Mirror(TreeNode root) {
    if (root == null)
        return root;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        // 交换当前节点的左右子指针
        TreeNode t = node.left;
        node.left = node.right;
        node.right = t;
        if (node.left != null)
            stack.push(node.left);
        if (node.right != null)
            stack.push(node.right);
    }
    return root;
}

该版本将递归栈替换为堆上分配的显式栈，最坏空间仍是 O(n)，但不再受 JVM 调用栈深度限制，是生产代码中更稳健的写法。它与递归版严格等价：两者都是"访问一个节点就立刻交换其左右指针"，只是访问顺序由系统栈改由程序栈驱动。

五、替代思路：非破坏式地构造新镜像树

原题约束是在原树上操作，但在实际业务代码中更常见的需求是"返回一棵镜像树、保留原树不变"。此时不需要 swap 交换指针，只需按镜像顺序复制节点：

public TreeNode mirrorCopy(TreeNode root) {
    if (root == null)
        return null;
    TreeNode mirror = new TreeNode(root.val);
    // 注意：新左孩子 = 原右孩子的镜像；新右孩子 = 原左孩子的镜像
    mirror.left = mirrorCopy(root.right);
    mirror.right = mirrorCopy(root.left);
    return mirror;
}

关键在于子树的对应关系是交叉递归的：原树左子树的镜像成为新树的右子树，原树右子树的镜像成为新树的左子树。时间 O(n)、空间 O(n)（新树节点）+ O(h)（递归栈）。如果只需要镜像树的前序遍历序列而不需要真实树结构，还可以只返回交换后的遍历序列，进一步节省空间。

六、边界条件与结果验证

写完后建议按以下清单自检：

1. 空树：root == null 直接返回，不抛异常——两个版本都显式处理了这一分支。
2. 单节点树：swap 后左右均为 null，树形不变，符合镜像定义。
3. 单侧子树（退化的"链"）：节点交换后仍然保持链形态，只是父子关系不变、树形不变——这正是单侧子树的镜像等于其本身的几何性质，可用来反向验证。
4. 结果验证方法：对原树与镜像结果分别做前序遍历，两序列应满足"互为镜像"关系；更直接的验证是结合姊妹题 对称的二叉树 的思路——对一棵树做两次镜像应还原为原树（镜像的逆映射是它自身），即 Mirror(Mirror(root)) 与原树的前序遍历序列一致。这一"二次镜像恒等"性质也说明了 swap 操作是对合（involution）。

七、在 CS-Notes 中的延伸路线

本题属于树类递归的入门实战，按 剑指 Offer 题解 - 目录 的编排，掌握后可以继续练习：

• 28. 对称的二叉树：双参数递归判定两棵子树是否互为镜像，递归结构是本题的直接变体；
• 7. 重建二叉树：遍历序列还原结构，递归 + 边界处理的进阶应用；
• 37. 序列化二叉树：遍历顺序与树结构的双向转换，与前序/后序框架一脉相承；
• 55.1 二叉树的深度：与本题共享 O(h) 递归深度分析框架。

八、小结

实现	是否修改原树	时间	空间	风险
递归 + swap（原题解法）	是	O(n)	O(h) 调用栈	极端不平衡时栈溢出
显式栈迭代	是	O(n)	O(n) 堆栈	无栈溢出风险
非破坏式构造新树	否	O(n)	O(n) 新节点 + O(h) 栈	额外内存占用

三种写法共享同一不变式：每个节点在且仅被处理一次，处理内容就是"左右指针互换"（原树版）或"按交叉顺序复制"（新树版）。面试中先给出递归版并说明 O(n)/O(h) 复杂度，再主动补充迭代版应对栈溢出，是对这道题最完整的作答。