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;
|