LeetCode 剑指 Offer 27. 二叉树的镜像

2022-04-19 HGNULB 约 5 分钟

文章信息 17 个分类 5 个标签

分类

LeetCode CodeTop 简单已解决已掌握 20-50 字节跳动美团阿里巴巴快手猿辅导滴滴拼多多商汤虾皮剑指 Offer 剑指 Offer（第 2 版）

题目描述

✅ 剑指 Offer 27. 二叉树的镜像

题意分析

输入一棵二叉树的根节点，要求把它变成「镜像」的样子并返回根节点。所谓镜像，就是把这棵树想象成画在纸上，沿着过根节点的竖直轴翻转一次之后得到的形状：原来在左边的整棵子树跑到右边去，原来在右边的整棵子树跑到左边来。

这里有个容易读错的地方。镜像不是只把根的两个孩子调换，也不是只把叶子层重排，而是每一个节点的左右孩子都要调换。翻转是从根一路贯穿到叶子的。

约束信号方面，题目要的是返回根节点而不是返回新树，说明允许直接在原树上修改，不必额外开辟节点；节点值本身在整个过程中不参与任何比较或计算，真正被改动的只有指针。至于规模，二叉树类题目通常节点数在 $10^4$ 到 $10^5$ 量级，$O(n)$ 的做法足够，但递归深度在链状树上会退化到 $O(n)$，这一点值得在面试中主动提一句。

边界情形有三种：空树直接返回空；单节点树没有孩子可换，原样返回；只有一侧孩子的节点，交换后变成只有另一侧有孩子，null 同样要参与交换，不能因为某一侧为空就跳过。

解法：递归交换左右子树

核心思路

问题关键：镜像不是只交换根节点，而是让每个节点的左右子树都互换。这个定义对任意子树完全相同，天然适合递归。

为什么原地递归：题目不要求保留原树，节点值也不变，只需交换左右指针；新建整棵树会多占 $O(n)$ 空间。对当前节点交换孩子后，再递归处理交换后的两棵子树即可。

递归语义：mirrorTree(root) 返回时，以 root 为根的整棵子树已经完成镜像，且仍使用原来的节点。空节点直接满足该语义。

正确性：对树高归纳。空树显然正确；假设两棵更矮的子树都能被正确镜像，当前层先交换左右位置，再分别镜像其内部结构，得到的正是整棵树关于根的镜像。因此递归到根时全树正确。

解题步骤

若 root 为空，直接返回 null。

借助临时变量交换 root.left 与 root.right；Go 可用多重赋值。

递归镜像交换后的左、右子树。

返回原根节点 root。

口述样例：树 [4,2,7,1,3,6,9] 先把根的孩子换成 7、2，再把子树 7(6,9) 变为 7(9,6)、2(1,3) 变为 2(3,1)，结果为 [4,7,2,9,6,3,1]。

边界检查：空树返回 null；单节点不变；只有左孩子的节点镜像后应只有右孩子，说明 null 也必须参与交换。

代码实现

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)$。

关键点总结

先明确递归函数的语义，再按“当前节点操作 + 子问题”写代码。

本题原地修改输入树；若调用方需要保留原树，才应另行深拷贝。

交换引用必须用临时变量或多重赋值，不能连续覆盖。

DFS、BFS 的访问顺序都不影响结果；若担心链状树递归栈过深，可改用显式栈或队列。

易错点总结

连续写 root.left = root.right; root.right = root.left：原左子树引用已丢失，两个孩子会指向同一节点。

只交换根节点：三层树的更深层仍保持原方向，必须递归到每个节点。

交换后又递归旧引用且重复其中一侧：可能导致一棵子树翻转两次、另一棵未翻转；应统一递归交换后的两个孩子。

忘记空节点出口：叶子节点继续递归时会触发空指针异常。

忽略原地修改语义：调用结束后输入树本身已经改变，后续若仍依赖原结构会得到错误结果。

相似题目

题目	难度	考察点
226. 翻转二叉树	简单	与本题完全同题，只是函数名不同，可直接套用同一份代码
101. 对称二叉树	简单	只判断是否已经对称而不做修改，需双指针同时下探并交叉比较，不能改动原树
剑指 Offer 28. 对称的二叉树	简单	101 的同题，常与本题连问：先镜像再比较相等，还是一次遍历直接判对称
951. 翻转等价二叉树	中等	每个节点可选择翻转或不翻转，需在两种匹配方式间分支判等，是本题的决策版