大家好,我是程序员吴师兄,欢迎来到 图解剑指 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]
限制:
我们依旧用 四步分析法 进行结构化的分析。
二叉树的镜像指的是对于二叉树内任意一个节点,都交换了它的左右子节点。
比如下面这颗三层七节点的二叉树,首先交换左右子树。
交换后的左右子树的子节点还是保持原来的顺序,需要去交换左右子树自己的左右子树。
直接利用递归遍历二叉树,交换每个节点的左 / 右子节点,即可生成二叉树的镜像。
剑指 Offer 27. 二叉树的镜像.002
剑指 Offer 27. 二叉树的镜像.003
剑指 Offer 27. 二叉树的镜像.004
剑指 Offer 27. 二叉树的镜像.005
剑指 Offer 27. 二叉树的镜像.006
剑指 Offer 27. 二叉树的镜像.007
剑指 Offer 27. 二叉树的镜像.008
剑指 Offer 27. 二叉树的镜像.009
剑指 Offer 27. 二叉树的镜像.010
剑指 Offer 27. 二叉树的镜像.011
剑指 Offer 27. 二叉树的镜像.012
剑指 Offer 27. 二叉树的镜像.013
剑指 Offer 27. 二叉树的镜像.014
剑指 Offer 27. 二叉树的镜像.015
剑指 Offer 27. 二叉树的镜像.016
剑指 Offer 27. 二叉树的镜像.017
剑指 Offer 27. 二叉树的镜像.018
剑指 Offer 27. 二叉树的镜像.019
// 登录 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)。