输入一个二叉树，输出其镜像。
如下图，即交换所有节点的左右子树。
这里提供两种思路：使用递归和不使用递归。
使用的二叉树定义如下：
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}
}解决方法：
import java.util.LinkedList;
import java.util.Scanner;/** 题目描述：输入一个二叉树，输出其镜像。* */
public class Solution {Scanner scanner = new Scanner(System.in);// 建立二叉树public TreeNode createTree(TreeNode root) {String val;val = scanner.next(); // next方法每次取到一个间隔符前面的数据if(val.equals("#")) {return null;}root = new TreeNode(Integer.parseInt(val));// System.out.println("输入的数据为：" + val);root.left = createTree(root.left);root.right = createTree(root.right);return root;}// 得到二叉树的镜像 —— 递归的方式public void Mirror(TreeNode root) {if(root == null) {return;}if((root.left == null) && (root.right == null)) {return;}TreeNode temp = root.left;root.left = root.right;root.right = temp;Mirror(root.left);Mirror(root.right);}// 得到二叉树的镜像 —— 不使用递归public void MirrorNotRecursive(TreeNode root) {java.util.LinkedList<TreeNode> queue = new java.util.LinkedList<TreeNode>();TreeNode temp = null;if(root == null) {return;}queue.add(root);while(queue.size() != 0) {TreeNode node = queue.removeFirst();temp = node.left;node.left = node.right;node.right = temp;if(node.right != null) {queue.add(node.right); // 入队的为原来的左孩子}if(node.left != null) {queue.add(node.left);}}}// 层次遍历二叉树public void levelTraverse(TreeNode root) {if (root == null) {return;}LinkedList<TreeNode> list = new LinkedList<TreeNode>();list.add(root);while (list.size() != 0) {TreeNode node = list.removeFirst(); // list.removeFirst() 该方法LinkedList才有System.out.print(node.val + " ");if(node.left != null) {list.add(node.left); // list.add()添加单个元素，如果不指定索引的话，元素将被添加到链表的最后}if(node.right != null) {list.add(node.right);}}}public static void main(String[] args) {Solution solution = new Solution();TreeNode root = null;root = solution.createTree(root);System.out.println("原二叉树的层次遍历");solution.levelTraverse(root);solution.Mirror(root);System.out.println("\n输出该二叉树的镜像");solution.levelTraverse(root);solution.MirrorNotRecursive(root);System.out.println("\n输出该二叉树的镜像（非递归方式）");solution.levelTraverse(root);}
}/** 测试数据：* 1 2 3 # 4 # # 5 6 # # # 7 8 # # 9 10 # # 11 # # （说明：其中#说明左右子树为空）* 用先序遍历来建立树后，层次遍历结果为： 1 2 7 3 5 8 9 4 6 10 11* 反转二叉树之后：1 7 2 9 8 5 3 11 10 6 4 */上述程序的运行结果为：
这个代码除实现反转二叉树之外，还实现了先序建立二叉树及层次遍历二叉树，可参见上述代码。关于实现反转二叉树的两种方式，思路参考见下面陈述。
其中，递归的实现思路参考：http://zhidao.baidu.com/link?url=ohsjZowGYZokAf2wg7Q2w2UIZme_Tt1zuabVWGxFTfpzkmI0hC_BqBlhFAqsNSM3f0393lp0QEBMEp6WDTc0Na
void exchangeBTree(BTRee *root)
{BTRee *t;if(root){t=root->rChild;root->rChild=root->lChild;root->lChild=t;exchangeBTree(root->lChild);exchangeBTree(root->rChild);}
}
非递归的方式，参考自：
http://www.nowcoder.com/questionTerminal/bcffd7e8a0d4402c99773bed98690bb7?orderByHotValue=0&pos=1
是借助栈进行操作，栈是后进先出，我实现的时候用LinkedList模拟了队列（先进先出）。这里的区别在于左孩子和右孩子谁先进去，如果要左孩子先出来，可以区分对待：栈需要右孩子先压栈，然后再左孩子；如果是队列，则左孩子入队，然后再是右孩子。
void NonRecursive_Exchange(TreeNode *T)
{Stack s;TreeNode *p;if (NULL == T)return;InitStack(&s);Push(&s, T);while (!isEmpty(&s)){T = Pop(&s);p = T->left;T->left = T->right;T->right = p;if (T->right )Push(&s, T->right );if (T->left )Push(&s, T->left );}DestroyStack(&s);
}
最后，该题目可在牛客网进行练习，提交代码：http://www.nowcoder.com/books/coding-interviews/564f4c26aa584921bc75623e48ca3011
