/**
* 题目18：二叉树的镜像
* 操作给定的二叉树，将其变换为源二叉树的镜像。
* 输入描述： 二叉树的镜像定义：源二叉树
* 8
* /
* 6 10
* / \ /
* 5 7 9 11
* 镜像二叉树
* 8
* /
* 10 6
* / \ /
* 11 9 7 5
*/

@Test
public void test18(){
    //构建二叉树，其层次遍历：8、6、10、5、7、9、11
    TreeNode root = new TreeNode(8);
    root.left = new TreeNode(6);
    root.right = new TreeNode(10);
    root.left.left = new TreeNode(5);
    root.left.right = new TreeNode(7);
    root.right.left = new TreeNode(9);
    root.right.right = new TreeNode(11);
    //镜像
    Mirror_18_3(root);
    //利用队列进行层次遍历，并逐层输出节点
    System.out.print("After Mirror: ");
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);//加入根节点
    TreeNode tmp;
    while(!queue.isEmpty()){
        tmp = queue.poll();
        if(tmp.left!=null) queue.offer(tmp.left);
        if(tmp.right!=null) queue.offer(tmp.right);
        System.out.print(tmp.val+"\t");
    }
}
//解法1：递归解法。将左右节点互换、再将以左右节点为根节点的左右子树进行镜像即可 19ms
public void Mirror_18(TreeNode root) {
    if(root == null) return;
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    Mirror_18(root.left);
    Mirror_18(root.right);
}

/**解法2：非递归法，通过层次遍历，将左右节点互换（镜像过程如下）  36ms
 *        8                                   8                                8
 *       /  \                                /  \                             /  \
 *      6   10  (交换第一层节点的左右子树)=> 10    6(交换第一层节点的左右子树)=> 10    6
 *     / \  / \                            / \  / \                         / \  / \
 *    5  7 9 11                           9 11 5  7                        11 9 7  5
 */
public void Mirror_18_2(TreeNode root) {
    if(root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);//加入根节点
    TreeNode cur, tmp;
    while(!queue.isEmpty()){
        int k = queue.size();//本层中的节点个数
        while(k--!=0){
            cur = queue.poll();
            tmp = cur.left;
            cur.left = cur.right;
            cur.right = tmp;
            if(cur.left!=null) queue.offer(cur.left);
            if(cur.right!=null) queue.offer(cur.right);
        }
    }
}
//解法2的深度优先遍历（使用栈） 19ms
public void Mirror_18_3(TreeNode root) {
    if(root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);//加入根节点
    TreeNode cur, tmp;
    while(!stack.isEmpty()){
        cur = stack.pop();
        tmp = cur.left;
        cur.left = cur.right;
        cur.right = tmp;
        if(cur.left!=null) stack.push(cur.left);
        if(cur.right!=null) stack.push(cur.right);
    }
}