h*********i
发帖数: 2605 | 1 我知道可以用queue作BFS，但是如何在level结束后换行呢？ |
g*******y
发帖数: 1930 | 2 加一个control bit,控制是否打印newline
原来的queue
现在变为queue> |
i******t
发帖数: 370 | 3 把null作为分隔符push到queue里头，每次见到null，换行。每次pop一个node N，如果
queue里下一个是null，说明N是同一level的最后一个，push完N的children之后再push
一个null
【在 h*********i 的大作中提到】
: 我知道可以用queue作BFS，但是如何在level结束后换行呢？
|
h*********i
发帖数: 2605 | 4 谁来set这个control bit?
1
/ \
2 3
/ \
4 5
比方说5应该set control bit，但是2怎么知道他的right child is the last in the
next level?
【在 g*******y 的大作中提到】
: 加一个control bit,控制是否打印newline
: 原来的queue
: 现在变为queue>
|
h*********i
发帖数: 2605 | 5 这个方法我也想过，就是最后的null要处理好，不注意会死循环，呵呵。
还有就是不太elegent。
push
【在 i******t 的大作中提到】
: 把null作为分隔符push到queue里头，每次见到null，换行。每次pop一个node N，如果
: queue里下一个是null，说明N是同一level的最后一个，push完N的children之后再push
: 一个null
|
b*******e
发帖数: 287 | 6 用queue, 并且记下入queue的节点地depth. 打印的时候边打印边比较当前打印level根
打印节点的level，不一样的换行，并且increase当前level. |
g*******y
发帖数: 1930 | 7 我想了下，还是分隔符比较好，呵呵
【在 h*********i 的大作中提到】
: 这个方法我也想过，就是最后的null要处理好，不注意会死循环，呵呵。
: 还有就是不太elegent。
:
: push
|
i******t
发帖数: 370 | 8 他这个要把control bit改成depth才work吧
the
【在 h*********i 的大作中提到】
: 谁来set这个control bit?
: 1
: / \
: 2 3
: / \
: 4 5
: 比方说5应该set control bit，但是2怎么知道他的right child is the last in the
: next level?
|
|
g*******y
发帖数: 1930 | 9 对的。
这个方法是我以前做一道完全二叉树/DFS的时候的方法，昨天面挂了过度沮丧，今天就头晕了随口说了。。。
【在 i******t 的大作中提到】
: 他这个要把control bit改成depth才work吧
:
: the
|
i******t
发帖数: 370 | 10 cmft...pat pat
【在 g*******y 的大作中提到】
: 对的。
: 这个方法是我以前做一道完全二叉树/DFS的时候的方法，昨天面挂了过度沮丧，今天就头晕了随口说了。。。
|
|
|
H*M
发帖数: 1268 | 11 u r good
dont worry
u will find a better one...
i remember u mentioned it is google? They kinda asks some linux command stuf
f, which sometimes is bad for non-cs-ers.
【在 g*******y 的大作中提到】
: 对的。
: 这个方法是我以前做一道完全二叉树/DFS的时候的方法，昨天面挂了过度沮丧，今天就头晕了随口说了。。。
|
m*****f
发帖数: 1243 | 12 怎么会挂的? 详细说说?
【在 g*******y 的大作中提到】
: 对的。
: 这个方法是我以前做一道完全二叉树/DFS的时候的方法，昨天面挂了过度沮丧，今天就头晕了随口说了。。。
|
g*******y
发帖数: 1930 | 13 是MS的on campus，没料到会出那么简单的题，一激动加紧张，慌着早点写完好接着做
后面的题，写了个居烂无比的code，很多情况都没考虑(平时练习的时候我都肯定能考
虑全的)。做完了时间还有一半，考官没继续出题，开始跟我聊天了，我也忘了该再要
一道题来做。。。唉。。。
【在 m*****f 的大作中提到】
: 怎么会挂的? 详细说说?
|
s*x
发帖数: 3328 | 14 保存一个标记在queue里边，初始的时候是root，标记。以后每次读出标记，都把标记
再扔回去，同时换行。比如你前面的那个例子
1
2 3
4 5
queue 的变化就是：
| 1 queue |
1 | queue 2 3 |
1 nl | 2 3 queue |
1 nl 2 | 3 queue 4 5 |
1 nl 2 3 | queue 4 5 |
1 nl 2 3 nl | 4 5 queue |
1 nl 2 3 nl 4 | 5 queue |
1 nl 2 3 nl 4 5 | queue |
1 nl 2 3 nl 4 5 nl | queue |
fin
【在 h*********i 的大作中提到】
: 我知道可以用queue作BFS，但是如何在level结束后换行呢？
|
s*******e
发帖数: 174 | 15 这个用 recursive 就可以print 出换行。。 |
s*******e
发帖数: 174 | 16 public void printTree(TreeNode root)
{
for(int i=0;;i++) {
if(printLevel(root,i,0)) System.out.println();
else break;
}
}
private boolean printLevel(TreeNode root, int level, int currentLevel) {
if(root==null) return false;
if(level==currentLevel)
{
System.out.print(root.value + " ");
return true;
}
else if(currentLevel < level)
{
return printLevel(root.left,level,currentLevel+1)&&
printLevel(root.right,level,currentLevel+1);
}
else |
g*******y
发帖数: 1930 | 17 O(N^2)？
【在 s*******e 的大作中提到】
: public void printTree(TreeNode root)
: {
: for(int i=0;;i++) {
: if(printLevel(root,i,0)) System.out.println();
: else break;
: }
: }
:
: private boolean printLevel(TreeNode root, int level, int currentLevel) {
: if(root==null) return false;
|
U**********y
发帖数: 194 | 18 牛
【在 s*******e 的大作中提到】
: public void printTree(TreeNode root)
: {
: for(int i=0;;i++) {
: if(printLevel(root,i,0)) System.out.println();
: else break;
: }
: }
:
: private boolean printLevel(TreeNode root, int level, int currentLevel) {
: if(root==null) return false;
|
p******m
发帖数: 544 | 19
“return printLevel(root.left,level,currentLevel+1)&&
printLevel(root.right,level,currentLevel+1);”
这个有點问题吧，如果某个node 没有right 或者 left, 会返回false，那么整个的就
退出了。
应该是：
left = printLevel(root.left, level, currentLevel+1);
right = printLevel(root.right, level, currentLevel+1);
return left || right;
！
【在 s*******e 的大作中提到】
: public void printTree(TreeNode root)
: {
: for(int i=0;;i++) {
: if(printLevel(root,i,0)) System.out.println();
: else break;
: }
: }
:
: private boolean printLevel(TreeNode root, int level, int currentLevel) {
: if(root==null) return false;
|
