[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()); } }}
页:
[1]