二叉树的镜像

1.题目：
操作给定的二叉树，将其变换为源二叉树的镜像。

二叉树的镜像定义：源二叉树 
            8
           /  \
          6   10
         / \  / \
        5  7 9 11
        镜像二叉树
            8
           /  \
          10   6
         / \  / \
        11 9 7  5

2.思路：
方法一：递归，最为简单的方式；时间复杂度O(n)

public class Solution {
    public void Mirror(TreeNode root) {
        //递归结束的标记
        if(root==null){
            return ;
        }
        //递归目的：交换的经典操作
        TreeNode tempNode;
        tempNode=root.left;
        root.left=root.right;
        root.right=tempNode;
        //左右子树递归
        Mirror(root.left);
        Mirror(root.right);
    }
}

方法二：非递归的方法，使用一个while循环解决
镜像就是将“根”节点的左右两个“子”节点互换，类似于数组的元素交换（运用临时节点temp），利用二叉树的广度优先搜索即可

import java.util.Queue;
import java.util.LinkedList;
public class Solution {
    public void Mirror(TreeNode root) {
        if(root==null){
            return;
        }
        Queue<TreeNode> nodes=new LinkedList<>();//利用队列临时存储
        TreeNode curr;//记录现在的节点
        TreeNode temp;//临时节点
        nodes.offer(root);//入队列
        while(!nodes.isEmpty()){//如果不为空，继续交换
        curr=nodes.poll();//出队列
        temp=curr.left;
        curr.left=curr.right;
        curr.right=temp;
        if(curr.left!=null){
        nodes.offer(curr.left);
        }
        if(curr.right!=null){
        nodes.offer(curr.right);
        }
        }
    }
}