陈荣莲 发表于 2013-8-16 11:06:59

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

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

秦静静 发表于 2013-8-16 11:11:23

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]
查看完整版本: [Microsoft面试]题目:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。