LeetCode 剑指 Offer 27. 二叉树的镜像
题目描述
题意分析
返回给定二叉树的镜像：从根到任一节点的路径上，原来向左的选择改为向右，原来向右的选择改为向左。节点值和节点数量都不变，变化的是每个节点左右孩子的位置。
当前实现直接修改输入树的连接关系，返回的仍是原根节点。空树的镜像仍为空，只有一侧孩子的节点也需要交换，不能只处理左右孩子都存在的情况。
解法：递归交换左右子树
核心思路
[!blue]
对任意子树，镜像后的左子树应当是原右子树的镜像，右子树应当是原左子树的镜像。这个定义在整棵树与任一子树上都相同，因此适合递归。
约定
mirrorTree(root)原地完成以root为根的整棵子树的镜像，并返回这个根。先交换当前节点的左右孩子，确定这一层的新方向；再分别递归处理交换后的两个孩子，让它们内部也全部镜像。空节点直接返回，叶子的两个空孩子交换后仍为空。从最底层向上看，只要两个子树内部已经按递归约定镜像，配合当前层的交换就得到整棵子树的正确镜像，最终覆盖所有节点。
Java 交换前必须保存原来的左孩子，避免连续赋值时丢失其中一棵子树；Go 的多重赋值会先读取两个旧引用。交换的是引用，不是节点值，因此整个子树会随孩子引用一起移动。
解题步骤
- 若
root为空，直接返回空引用。- 用临时变量或多重赋值交换
root.left与root.right，空孩子也参与交换。- 递归镜像交换后的左子树和右子树，每一侧只处理一次。
- 返回当前根节点。所有修改已经发生在原树上，不需要重新构造节点。
代码实现
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
// 先保存原左子树，再交换两条引用，避免覆盖后丢失节点。
TreeNode left = root.left;
root.left = root.right;
root.right = left;
// 当前层交换后，继续镜像两个完整子树。
mirrorTree(root.left);
mirrorTree(root.right);
return root;
}
}
func mirrorTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
// 交换孩子引用后，继续镜像两个完整子树。
root.Left, root.Right = root.Right, root.Left
mirrorTree(root.Left)
mirrorTree(root.Right)
return root
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点恰好交换一次左右孩子。
- 空间复杂度：$O(h)$，
h为树高，来自递归栈；平衡树为 $O(\log n)$，链状树最坏为 $O(n)$。
关键点总结
[!green]
- 先明确递归函数的语义，再按“当前节点操作 + 子问题”写代码。
- 返回值仍是原根节点，输入树的孩子引用已经被修改。
- 交换引用必须用临时变量或多重赋值，不能连续覆盖。
易错点总结
[!yellow]
- 连续写
root.left = root.right; root.right = root.left：原左子树引用已丢失，两个孩子会指向同一节点。- 只交换根节点：三层树的更深层仍保持原方向，必须递归到每个节点。
- 交换后又递归旧引用且重复其中一侧：可能导致一棵子树翻转两次、另一棵未翻转；应统一递归交换后的两个孩子。
- 忘记空节点出口：叶子节点继续递归时会触发空指针异常。
- 忽略原地修改语义：调用结束后输入树本身已经改变，后续若仍依赖原结构会得到错误结果。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 101. 对称二叉树 | 简单 | 对称性可以看作原树与镜像相同，本题实际生成镜像结构。 |
| 156. 上下翻转二叉树 | 中等 | 原题把最左链向上翻转并改变父子关系，本题只在每个节点交换左右孩子。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！