第一遍刷剑指offer，每一题都会把具体的思路，以及在网上寻找的优化的点，还有自己二刷三刷之后的想法分享出来。
首先是最简单的一个热身的题-----二叉树镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
递归方式：
public class Solution {
public void Mirror(TreeNode root) {
if(root == null){
return;
}
TreeNode tempNode = root.right;
root.right = root.left;
root.left = tempNode;
Mirror(root.right);
Mirror(root.left);
}
}
这种方式很简单，仅仅需要一个TreeNode变量做中间替换，额外空间需求较低，但是在函数调用的过程中，由于是递归的方式，需要一个比较大的函数调用栈，所以也是耗用一定的空间。
遍历方式
public class Solution {
public void Mirror(TreeNode root) {
if(root == null){
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
TreeNode temp = null;
while(!stack.empty()){
root = stack.pop();
temp = root.left;
root.left = root.right;
root.right = temp;
if(root.left != null){
stack.push(root.left);
}
if(root.right != null){
stack.push(root.right);
}
}
}
因为要交换每一个节点的两个子节点的位置，遍历的时候为了保证每个树的节点都被遍历到，应该使用常规的深度优先遍历或者广度优先遍历（在这提一下，使用深度优先遍历一般是用栈来实现的，广度优先遍历使用队列来实现的。在这里我们使用深度优先）
这里我们选择使用栈，先来复习一下jdk中提供的stack数据结构的api。
很简单
StackAPI.png
它只有5个方法
使用遍历的方式解答这个问题，要注意的几个关键的点
- 循环的结束条件为栈为空。
- 在OJ中，是没有自动导入包功能的，所以当需要引入一些集合框架中的数据结构的时候OJ需要手动的将类import进来。
- java中Stack对象的push支持null元素，当你push进一个null之后，size会+1，所以在向栈中添加节点的时候要注意判空。
