标题: [Microsoft面试]题目：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。 [打印本页] 作者: 陈荣莲 时间: 2013-8-16 11:06 标题: [Microsoft面试]题目：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。 用递归和循环两种方法完成树的镜像转换。 要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入8/ \6 10/ \ / \5 7 9 11输出8 6 10 5 7 9 11。作者: 秦静静 时间: 2013-8-16 11: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()); } }}