剑指Offer_#27_二叉树的镜像
Contents
题目
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
4
/
2 7
/ /
1 3 6 9
镜像输出：
4
/
7 2
/ /
9 6 3 1思路分析
算法流程
遍历所有节点，如果遍历到的节点有子节点，就交换它的两个子节点。 交换完所有子节点，就得到了树的镜像。
对树进行遍历，有递归和迭代（栈辅助） 两种方式，接下来分别分析两种方法。
方法1：递归
递归函数的作用是，输入一个子树的根节点，返回这个子树的镜像。
TreeNode mirrorTree(TreeNode root)- 特殊情况
- 输入子树为null,即空树，返回null。
- 出口条件
- 输入的
root没有子节点，说明整个树都遍历完了，返回root（叶子节点）本身
- 输入的
- 递推过程
1. 交换root的左右子树，即交换root.left和root.right
2. 对左右子树本身求镜像 - 回溯返回值
- 返回
root的镜像，即经过上述处理的root
- 返回
递推过程
从根节点开始，遍历所有节点，在递归调用的位置处被阻塞住。
直到访问到叶子节点，满足出口条件，直接返回叶子节点本身。
回溯过程
返回上级的递归调用，从阻塞位置继续执行。将叶子节点拼接到所属子树根节点上，返回子树。
依次类推，直到回溯到整棵树的根节点，返回值就是整棵树的镜像。
方法2：迭代（栈辅助）
使用栈来辅助遍历的过程。栈的作用是保存待访问节点的指针(引用)。
为什么需要单独用一个栈来保存节点的指针呢？
- 对于数组/链表这类型的数据结构，一个元素有且只有一个相邻的元素，所以遍历的时候是单向的。
- 数组访问下一个元素，只需将当前下标加1即可。
- 链表访问下一个元素，只需访问当前元素的
next指针即可。 - 在这里边，其实用到了辅助变量，分别是数组下标，
next指针，他们的作用是保存待访问节点的指针(引用)
- 二叉树与数组/链表相比，每个节点有两个子节点，所以用单一的辅助变量去控制遍历过程就比较困难了。所以想到可以用栈这种数据结构去保存待访问节点的指针(引用)，作为一种容器，可以保存很多节点的指针。
同理，用和栈类似的队列数据结构，也可以完成非递归遍历的过程。
算法流程
- 特例处理： 当 root 为空时，直接返回 null ；
- 初始化： 栈（或队列），本文用栈，并加入根节点 root 。
- 循环交换： 当栈 stack 为空时跳出；
- 出栈： 记为 node (当前访问到了node,就可以将其弹出)；
- 添加子节点： 将 node 左和右子节点入栈（继续访问node的左节点和右节点）；
- 交换： 交换 node 的左 / 右子节点。
解答1：递归
class Solution {
public TreeNode mirrorTree(TreeNode root) {
//特殊情况：空树
if(root == null) return null;
//出口条件：遇到叶节点
if(root.left == null && root.right == null) return root;
//递推过程，交换root.left和root.right子树
//但是左右子树本身还没有进行镜像
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
//返回值：继续求root.left和root.right子树的镜像
//如果是null,镜像就是null
root.left = mirrorTree(root.left);
root.right = mirrorTree(root.right);
return root;
}
}解答2：迭代（栈辅助）
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
//泛型collection对象的实例化，右侧不需要写类型
Stack<TreeNode> stack = new Stack<>();
stack.add(root);
while(!stack.isEmpty()){
//当前节点node出栈
TreeNode node = stack.pop();
//如果node是叶节点，那么不会入栈，栈最后变空，循环结束
//node的左右子节点入栈，代表这是还未访问到的，以后访问
if(node.left != null) stack.add(node.left);
if(node.right != null) stack.add(node.right);
//交换node的左右子树
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
}
return root;
}
}