剑指 Offer 27. 二叉树的镜像
一、题目描述
请完成一个函数,输入一个二叉树,该函数输出它的镜像。
例如输入:
4
/ \
2 7
/ \ / \
1 3 6 9
镜像输出:
4
/ \
7 2
/ \ / \
9 6 3 1
示例 1:
输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]
二、题目解析
二叉树的镜像指的是对于二叉树内任意一个节点,都交换了它的左右子节点。
比如下面这颗三层七节点的二叉树,首先交换左右子树。
交换后的左右子树的子节点还是保持原来的顺序,需要去交换左右子树自己的左右子树。
为了帮助你更好的理解整个过程,我特意做了一组动画,点开可以查看:
三、参考代码
// 登录 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;
}
}