大家好，我是程序员吴师兄，欢迎来到 图解剑指 Offer 结构化专栏，在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码，希望能帮助你即使在面试的时候紧张也能做对。
AlgoMooc 算法慕课网，每道题目都有动画和图片，致力于帮助每个程序员通过算法面试！
今天分享的题目来源于 LeetCode 上的剑指 Offer 系列面试题 27. 二叉树的镜像。
题目汇总链接：https://www.algomooc.com/jianzhioffer
一、题目描述
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
限制：
- 0 <= 节点个数 <= 1000
二、题目解析
我们依旧用 四步分析法 进行结构化的分析。
- 模拟：模拟题目的运行。
- 规律：尝试总结出题目的一般规律和特点。
- 匹配：找到符合这些特点的数据结构与算法。
- 边界：考虑特殊情况。
1、模拟
二叉树的镜像指的是对于二叉树内任意一个节点，都交换了它的左右子节点。
比如下面这颗三层七节点的二叉树，首先交换左右子树。
交换后的左右子树的子节点还是保持原来的顺序，需要去交换左右子树自己的左右子树。
2、规律
直接利用递归遍历二叉树，交换每个节点的左 / 右子节点，即可生成二叉树的镜像。
3、匹配
- 递归
4、边界
- 二叉树为空
三、动画描述
隐藏内容
此处内容需要权限查看
会员免费查看四、图片描述
五、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
public TreeNode mirrorTree(TreeNode root) {
// 当节点为空时，直接返回
if(root == null) return null;
// 设置一个临时的节点 tmp 用来存储当前节点的左子树
TreeNode tmp = root.left;
// 以下两个操作是在交换当前节点的左右子树
// 当前节点的左子树为节点的右子树
// 同时递归下去，不停的交互子树中的节点
root.left = mirrorTree(root.right);
// 当前节点的右子树为节点的左子树
// 同时递归下去，不停的交互子树中的节点
root.right = mirrorTree(tmp);
// 最后返回根节点
return root;
}
}
六、复杂度分析
时间复杂度
时间复杂度为 O(N)。
空间复杂度
空间复杂度为 O(N)。
七、相关标签
- 树
- 递归
