[Microsoft面试]题目：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。

用递归和循环两种方法完成树的镜像转换。 要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入8/ \6 10/ \ / \5 7 9 11输出8 6 10 5 7 9 11。

The nodes inthe levels are printed in the similar manner their parents were printed. So itshould be an FIFO queue to hold the level. I really don’t remember the functionname of the stl queue, so I will write it in Java...void printByLevel(Node root) {  Node sentinel = new Node();  LinkedList<Node> q=newLinkedList<Node>();  q.addFirst(root); q.addFirst(sentinel);  while (!q.isEmpty()) {    Node n = q.removeLast();    if (n==sentinel) {     System.out.println(“\n”);     q.addFirst(sentinel);    } else {     System.out.println(n);      if (n.left() !=null) q.addFirst(n.left());      if(n.right()!=null) q.addFirst(n.right());     }     }}