求教一道经典面题的解法 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求教一道经典面题的解法

求教一道经典面题的解法# JobHunting - 待字闺中

D*62010-05-27 07:05

1 楼

print binary tree in level order, starting from the top, an alternate is
starting from the lowest level. Starting a new line for each level.
这题是不是就用个queue 加个 counter, count读到的node数量, print the new line
when counter gets to 1, 2, 4, 8, .....还有就是children是null也要加到
queue里去make sure counter behaves correct.
大家都是这么做的吗? 有啥其他的方法吗?
谢谢

z*n2010-05-27 07:05

2 楼

complete binary tree才能用1， 2， 4， 8
从顶上开始打印的话，再将root放入queue后，放一个newline的标志进入queue（比如一
个特殊node），以后循环处理queue的时候，遇到这个newline标志就打印个newline，然
后把这个newline标志重新放入queue（这时它出现在queue最后，表示下一次要打印new
line的时候）

line

【在 D****6 的大作中提到】

: print binary tree in level order, starting from the top, an alternate is
: starting from the lowest level. Starting a new line for each level.
: 这题是不是就用个queue 加个 counter, count读到的node数量, print the new line
: when counter gets to 1, 2, 4, 8, .....还有就是children是null也要加到
: queue里去make sure counter behaves correct.
: 大家都是这么做的吗? 有啥其他的方法吗?
: 谢谢

r*o2010-05-27 07:05

3 楼

如果要从底部开始打印呢？是不是要把这些结果放到stack里面先?

如一
，然
new

【在 z****n 的大作中提到】

: complete binary tree才能用1， 2， 4， 8
: 从顶上开始打印的话，再将root放入queue后，放一个newline的标志进入queue（比如一
: 个特殊node），以后循环处理queue的时候，遇到这个newline标志就打印个newline，然
: 后把这个newline标志重新放入queue（这时它出现在queue最后，表示下一次要打印new
: line的时候）
:
: line

z*n2010-05-27 07:05

4 楼

恩，就是处理queue的时候，不直接打印，放到一个stack里面，然后从stack里打印，不
过这样的话，每一行的顺序都反了。要是还要求每一行的顺序跟原来一样。。。貌似没
有什么简洁漂亮的方法。。。

【在 r****o 的大作中提到】

: 如果要从底部开始打印呢？是不是要把这些结果放到stack里面先?
:
: 如一
: ，然
: new

z*n2010-05-27 07:05

5 楼

要是从底层开始打印，并且还要维持每层顺序的话，貌似只能处理queue的时候，把每一
行加入另外一个queue，遇到newline，就把这另外一个queue整体作为一个对象放到另一
个stack里。。。

，不

【在 z****n 的大作中提到】

: 恩，就是处理queue的时候，不直接打印，放到一个stack里面，然后从stack里打印，不
: 过这样的话，每一行的顺序都反了。要是还要求每一行的顺序跟原来一样。。。貌似没
: 有什么简洁漂亮的方法。。。

r*o2010-05-27 07:05

6 楼

处理每行的时候反序将children节点放进qeueue里不行吗?

，不

【在 z****n 的大作中提到】

z*n2010-05-27 07:05

7 楼

恩，可以，土了。。。

【在 r****o 的大作中提到】

: 处理每行的时候反序将children节点放进qeueue里不行吗?
:
: ，不

c*y2010-05-27 07:05

8 楼

Can you implement the binary tree using an array, and then print out the
array?
Since the level numbers of the elements in the tree can be determined using
their positions in the array and they are placed in the array in the order
of level-increasing, it is easy to print out the elements in the same level.

line

【在 D****6 的大作中提到】

D*62010-05-27 07:05

9 楼

这个不太对吧, 每次add newline时是针对这个current node, 不是这个current level
, 所以还是需要1,2,4,8来分辨什么时候打newline. 不complete 也可以, 就需要把
null children也要add到queue里. 然后每次看到null就只是count++, continue.
我刚开始也push newline into the queue, then realize doesn't work!

如一
，然
new

【在 z****n 的大作中提到】

z*n2010-05-27 07:05

10 楼

如果看到null就是简单的count++，那么你的方法也可以
不过我的方法也是对的，你再琢磨琢磨：）

level

【在 D****6 的大作中提到】

: 这个不太对吧, 每次add newline时是针对这个current node, 不是这个current level
: , 所以还是需要1,2,4,8来分辨什么时候打newline. 不complete 也可以, 就需要把
: null children也要add到queue里. 然后每次看到null就只是count++, continue.
: 我刚开始也push newline into the queue, then realize doesn't work!
:
: 如一
: ，然
: new

D*62010-05-27 07:05

11 楼

明白了! 多谢!!

【在 z****n 的大作中提到】

: 如果看到null就是简单的count++，那么你的方法也可以
: 不过我的方法也是对的，你再琢磨琢磨：）
:
: level

s*n2010-05-27 07:05

12 楼

1.from top
Use two queues q1 and q2. Get a node from the first queue, print it, and
then push its children into the second queue.When the first queue is empty,
get nodes from the second queue and push their children into the first queue
, and so on...
2. from bottom
Use two queue q1 and q2, and one stack s1. The stack is used to store nodes.
When all nodes are visited, get nodes from the stack and print. Similarly
to the above, except that when you get a node from one queue, first push its
right

s*n2010-05-27 07:05

13 楼

2. from bottom
You need to insert a dummy node into the stack as line end mark.

t*h2010-05-27 07:05

14 楼

我一直用dummy node来做但是昨天看到有人说有更简单的方法请知道的赐教
我的做法是一个队列一个栈
循环开始前把root和dummy入队列
从队列里读结点
把这个点放到栈中然后把他的子结点入队列
当读到dummy时如果队列不为空再把dummy入队列压栈
如果队列为空则表示从栈中输出结果读到dummy时输出newline

h*k2010-05-27 07:05

15 楼

one queue is enough.

,
queue
nodes.
its

【在 s*****n 的大作中提到】

: 1.from top
: Use two queues q1 and q2. Get a node from the first queue, print it, and
: then push its children into the second queue.When the first queue is empty,
: get nodes from the second queue and push their children into the first queue
: , and so on...
: 2. from bottom
: Use two queue q1 and q2, and one stack s1. The stack is used to store nodes.
: When all nodes are visited, get nodes from the stack and print. Similarly
: to the above, except that when you get a node from one queue, first push its
: right

s*n2010-05-27 07:05

16 楼

Of course, one queue can do it. Using two queues is just to remove dummy
node in the queue.

a*d2010-05-27 07:05

17 楼

One queue does not save you anything.
The total number of elements are the same.

【在 h**k 的大作中提到】

: one queue is enough.
:
: ,
: queue
: nodes.
: its

k*i2010-05-27 07:05

18 楼

从root 分层打印可以这样写只需要一个queue和一个mark
void level_traversal(Node * root)
{
if (!root)
exit(0);
Queue my_queue = new Queue();
my_queue.push(root);
my_queue.push(Mark);

while (my_queue.empty())
{
Node tmp = my_queue.pop();

if (tmp==Mark)
{
my_queue.push(Mark);
Print("\n");
}
else
{
Print(tmp);
my_queue.push(root->left);
my

【在 D****6 的大作中提到】

h*h2010-05-27 07:05

19 楼

从root开始分层打印
在你代码修改了一下，不用mark. 我对C++不太了，明白我的idea就好。我在一个最后
哪到offer的公司onsite面到。临时想的，不保证最简单。当时用的是java.
void level_traversal(Node * root)
{
if (!root)
exit(0);
Queue my_queue = new Queue();
my_queue.push(root);
while (my_queue.empty())
{
int count = my_queue.size();
for(int i = 0; i < count; ++i){
Node tmp = my_queue.pop();
Print(tmp);
if(temp->left) my_queue.push(temp->left);
if(temp->right) my_queue.push(t

【在 k**********i 的大作中提到】

: 从root 分层打印可以这样写只需要一个queue和一个mark
: void level_traversal(Node * root)
: {
: if (!root)
: exit(0);
: Queue my_queue = new Queue();
: my_queue.push(root);
: my_queue.push(Mark);
:
:

a*g2010-05-27 07:05

20 楼

你这个不是通用queue了
常规的queue是不能直接调用size()的
当然，c++的deque是可以的

【在 h****h 的大作中提到】

: 从root开始分层打印
: 在你代码修改了一下，不用mark. 我对C++不太了，明白我的idea就好。我在一个最后
: 哪到offer的公司onsite面到。临时想的，不保证最简单。当时用的是java.
: void level_traversal(Node * root)
: {
: if (!root)
: exit(0);
: Queue my_queue = new Queue();
: my_queue.push(root);
: while (my_queue.empty())

h*h2010-05-27 07:05

21 楼

那个语言的queue不能调用size()?
C++的queue也可以调用size()啊。这个问题又用不到deque。
实在不准用size(), 自己count也行。
个人只是觉得用dummy node 太weird.

【在 a***g 的大作中提到】

: 你这个不是通用queue了
: 常规的queue是不能直接调用size()的
: 当然，c++的deque是可以的