r****o
发帖数: 1950 | 1 用书上通用的用queue的方法实现二叉树按层次打印，结果全打印到一行了。
不知道有没有什么好办法可以插入换行符，让每层数据在不同的行显示？ |
B*****t
发帖数: 335 | 2 add a flag when you push the right most node into the queue.
【在 r****o 的大作中提到】
: 用书上通用的用queue的方法实现二叉树按层次打印，结果全打印到一行了。
: 不知道有没有什么好办法可以插入换行符，让每层数据在不同的行显示？
|
r****o
发帖数: 1950 | 3 Thanks. But how to judge the right most node of each level?
【在 B*****t 的大作中提到】
: add a flag when you push the right most node into the queue.
|
B******5
发帖数: 4676 | |
r****o
发帖数: 1950 | 5 可以吧，这不是面试题，我自己想的。呵呵。
【在 B******5 的大作中提到】
: node上不能再加上一个层数的变量？
|
z*******y
发帖数: 578 | 6 昨天facebook phone screen的时候就让我写的这道coding
你可以把每层放进queue以后，再 queue.push 一个NULL来表示一层结束了
每次从queue里出来的元素，如果是NULL就换行，不是就接着打印
这里关键的一点是每次NULL从queue里边pop出来后，要push一个新的NULL到队列结尾
你先看看，还不明白的话我就把代码贴上来 |
r****o
发帖数: 1950 | 7
明白了，就是在这里实现了在每行末尾加个NULL，对把。
【在 z*******y 的大作中提到】
: 昨天facebook phone screen的时候就让我写的这道coding
: 你可以把每层放进queue以后，再 queue.push 一个NULL来表示一层结束了
: 每次从queue里出来的元素，如果是NULL就换行，不是就接着打印
: 这里关键的一点是每次NULL从queue里边pop出来后，要push一个新的NULL到队列结尾
: 你先看看，还不明白的话我就把代码贴上来
|
B*****t
发帖数: 335 | 8 ???
starting from the root, if it is right most node, push it with a flag(of
course root is right most node).
once you pop a right most node, and this node has right child, push that
child with a flag too.
【在 r****o 的大作中提到】
: Thanks. But how to judge the right most node of each level?
|
r****o
发帖数: 1950 | 9 the rightmost node in one level can also be the left child of a node in the
above level.
【在 B*****t 的大作中提到】
: ???
: starting from the root, if it is right most node, push it with a flag(of
: course root is right most node).
: once you pop a right most node, and this node has right child, push that
: child with a flag too.
|
B*****t
发帖数: 335 | 10 hehe, it's a trick, if right most node don't have right child, you can
create a dummy child, when output, remember don't output the content of the
dummy node.
the
【在 r****o 的大作中提到】
: the rightmost node in one level can also be the left child of a node in the
: above level.
|
|
|
B*****t
发帖数: 335 | 11 请问你facebook在哪儿投的简历？ thanks
【在 z*******y 的大作中提到】
: 昨天facebook phone screen的时候就让我写的这道coding
: 你可以把每层放进queue以后，再 queue.push 一个NULL来表示一层结束了
: 每次从queue里出来的元素，如果是NULL就换行，不是就接着打印
: 这里关键的一点是每次NULL从queue里边pop出来后，要push一个新的NULL到队列结尾
: 你先看看，还不明白的话我就把代码贴上来
|
r****o
发帖数: 1950 | 12 谢谢，我还有一个小地方没明白。
如果每次NULL从queue里面pop出来，再push一个新的NULL进队列，那么程序如何知道什
么时候结束呢？要不然最后就会陷入push pop NULL的死循环。
也许这个问题很简单，请指教。
【在 z*******y 的大作中提到】
: 昨天facebook phone screen的时候就让我写的这道coding
: 你可以把每层放进queue以后，再 queue.push 一个NULL来表示一层结束了
: 每次从queue里出来的元素，如果是NULL就换行，不是就接着打印
: 这里关键的一点是每次NULL从queue里边pop出来后，要push一个新的NULL到队列结尾
: 你先看看，还不明白的话我就把代码贴上来
|
z*******y
发帖数: 578 | 13 queue的初始化是把root放进去，然后再放进去一个NULL
然后循环条件是 while（！queue.empty()）
检查queue是否空了就可以
【在 r****o 的大作中提到】
: 谢谢，我还有一个小地方没明白。
: 如果每次NULL从queue里面pop出来，再push一个新的NULL进队列，那么程序如何知道什
: 么时候结束呢？要不然最后就会陷入push pop NULL的死循环。
: 也许这个问题很简单，请指教。
|
r****o
发帖数: 1950 | 14 但是不是至少有一个NULL在queue里面吗？因为每个NULL pop之后又会push 一个新的
NULL。
【在 z*******y 的大作中提到】
: queue的初始化是把root放进去，然后再放进去一个NULL
: 然后循环条件是 while（！queue.empty()）
: 检查queue是否空了就可以
|
m****u
发帖数: 3915 | 15 用两个queue
一个queue打印时，总是把孩子加入到另一个queue
queue空了就打印换行，然后换另一个queue打印
【在 r****o 的大作中提到】
: 用书上通用的用queue的方法实现二叉树按层次打印，结果全打印到一行了。
: 不知道有没有什么好办法可以插入换行符，让每层数据在不同的行显示？
|
r****o
发帖数: 1950 | 16 这个方法好，多谢。
【在 m****u 的大作中提到】
: 用两个queue
: 一个queue打印时，总是把孩子加入到另一个queue
: queue空了就打印换行，然后换另一个queue打印
|
r****o
发帖数: 1950 | 17 发现可以判断 queue.size()==1 && queue.front=＝NULL 时程序结束。
【在 z*******y 的大作中提到】
: queue的初始化是把root放进去，然后再放进去一个NULL
: 然后循环条件是 while（！queue.empty()）
: 检查queue是否空了就可以
|
d********e
发帖数: 132 | 18
请把代码贴上来吧，yahoo电面也问过我这道题。
【在 z*******y 的大作中提到】
: 昨天facebook phone screen的时候就让我写的这道coding
: 你可以把每层放进queue以后，再 queue.push 一个NULL来表示一层结束了
: 每次从queue里出来的元素，如果是NULL就换行，不是就接着打印
: 这里关键的一点是每次NULL从queue里边pop出来后，要push一个新的NULL到队列结尾
: 你先看看，还不明白的话我就把代码贴上来
|
z*******y
发帖数: 578 | 19 Void LevelTraversal(Node *root)
{
if(root == NULL) return;
queue q = new queue;
q.push(root);
q.push(NULL);
while(!q.empty() && q.size()!=1)
{
Node *temp = q.pop();
if(temp == NULL)
{
cout << endl;
q.push(NULL);
}
else
{
cout << temp->data << " ";
if(temp->left!=NULL)
q.push(temp->left);
if (temp->right!=NULL)
q.push(tem |
