微软算法100题15 求二元查找树的镜像

第15 题：
题目：输入一颗二元查找树，将该树转换为它的镜像，
即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入：
8
/
6 10
/ /
5 7 9 11
输出：
8
/
10 6
/ /
11 9 7 5

思路：

1.递归：根节点的镜像必然由其左子树的镜像和右子树的镜像组成，并将左子树的镜像置于根节点的右边，右子树的镜像放于根节点的左边，拿到左右子树，分别使用上述逻辑对其递归即可，递归的结束条件为如节点为空则返回null，如果是子节点则返回该子节点

2.非递归：从根节点开始，依次swap其左右分支节点，然后依次处理左右分支节点，因为要保留从根节点到左右分支节点的路径，可以用队列来完成这个逻辑, 队列的头结点为本次要处理的节点，将其出队列，并将其左右节点分别入队列，以便稍后处理

 1 package com.rui.microsoft;
 2 
 3 import java.util.ArrayDeque;
 4 import java.util.Deque;
 5 
 6 public class Test15_BSTMirror {
 7 
 8     public static void main(String[] args) {
 9         Node node4 = new Node(4);
10         Node node3 = new Node(3);
11         Node node5 = new Node(5);
12         Node node2 = new Node(2);
13         
14         node4.left = node3;
15         node4.right = node5;
16         node3.left = node2;
17         
18         midOrder(node4);
19         Node head = mirrorRec(node4);
20         //Node head = mirrorNonRec(node4);
21         System.out.println(" ");
22         midOrder(head);
23     }
24     
25     //Recursive
26     public static Node mirrorRec(Node node){
27         Node head = node;
28         if(null == head) return null;
29         //leaf
30         if(null == head.left && null == head.right) return head;
31         
32         Node left = head.left;
33         Node right = head.right;
34         head.right = mirrorRec(left);
35         head.left = mirrorRec(right);
36         return head;
37     }
38     
39     //Non-recursive
40     public static Node mirrorNonRec(Node node){
41         Node head = node;
42         
43         if(null == head) return null;
44         //leaf
45         if(null == head.left && null == head.right) return head;
46         
47         //Non-leaf
48         Deque<Node> queue = new ArrayDeque<Node>();
49         queue.offer(head);
50         
51         while(!queue.isEmpty()){
52             Node n = queue.poll();
53             Node left = n.left;
54             Node right = n.right;
55             if(null != left)queue.offer(left);
56             if(null != right)queue.offer(right);
57             n.left = right;
58             n.right = left;
59         }
60         
61         return head;
62     }
63     
64     public static void midOrder(Node head){
65         if(null == head) return;
66         midOrder(head.left);
67         System.out.print(" " + head.value);
68         midOrder(head.right);
69     }
70     
71     static class Node{
72         int value;
73         Node left;
74         Node right;
75         Node(int v){
76             this.value = v;
77         }
78     }
79 }