二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。假设题目所给的二叉树如下所示

解法一

思路很简单，既然要求镜像，只要将每一个结点的左右子结点交换一下位置就好了。使用中序遍历可以帮助我们实现这一想法

public class Solution { private TreeNode temp; public void Mirror(TreeNode root) { if(root == null) { return; } temp = root.left; root.left = root.right; root.right = temp; Mirror(root.left); Mirror(root.right); } }

解法二

解法一虽然简单粗暴，但如果碰到大数据就直接炸了。我们还是使用递归的思想，思考递归的时候不要一步步看它执行了啥，思考的方式应该是首先假设子问题都已经完美处理，然后只需要处理最终的问题即可。子问题的处理方式与最终那个处理方式一样，但是问题规模一定要逐渐缩小，最后给一个递归出口条件即可

对于本题，首先假设 root 的左右子树已经都处理好了，即左子树自身已经镜像了，右子树自身也镜像了，那么最后一步就是交换左右子树，问题解决。下面进入递归，就是处理子问题。子问题的处理方式与 root 一样，只是要缩小问题规模，所以只需要考虑 root.left 是什么情况，root.right 是什么情况即可

public class Solution { public void Mirror(TreeNode root) { // 为空则结束 if(root == null) { return; } // 假设 root 的左右子树都已经完成镜像了 // 那就让左右子树交换 swap(root); // 左子树做镜像操作 Mirror(root.left); // 右子树做镜像操作 Mirror(root.right); } private void swap(TreeNode node) { TreeNode temp = null; temp = node.left; node.left = node.right; node.right = temp; } }

当然，也可以使用栈来模拟上面的过程。开始执行方法时入栈，方法执行完毕时出栈

import java.util.Stack; public class Solution { private Stack<TreeNode> stack = new Stack<>(); public void Mirror(TreeNode root) { if(root == null) { return; } stack.push(root); while(!stack.empty()) { TreeNode node = stack.pop(); swap(node); if(node.left != null) { stack.push(node.left); } if(node.right != null) { stack.push(node.right); } } } private void swap(TreeNode node) { TreeNode temp = null; temp = node.left; node.left = node.right; node.right = temp; } }