剑指offer----二叉树的镜像

第一遍刷剑指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，所以在向栈中添加节点的时候要注意判空。