我来问个面经：打印binary tree 从root到leaf的所有path - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

我来问个面经：打印binary tree 从root到leaf的所有path

我来问个面经：打印binary tree 从root到leaf的所有path# JobHunting - 待字闺中

j*32015-09-01 07:09

1 楼

但是不能用recursion。
有人说，用stack, 我百思不得其解，这也不是pre/in order traverse, 咋用stack呢？
我想了一个办法，还是用queue，但是每个node换一个新class，带个parent。
可是这样就要造一个新class。
有什么办法还用原来的treenode么？

o*y2015-09-01 07:09

2 楼

Stack stack = new Stack();
List list = new ArrayList();
TreeNode cur = root, pre = null;
stack.push(cur);
while(!stack.isEmpty()){
cur = stack.peek();
if((cur.left == null && cur.right == null) || (pre != null && (
cur.left == pre || cur.right == pre))){
cur = stack.pop();
if(cur.left == null && cur.right == null){
list.add(cur);
printPath(list);
}
list.remove(list.size()-1);
pre = cur;
}else{
if(cur.right != null)
stack.push(cur.right);
if(cur.left != null)
stack.push(cur.left);
list.add(cur);
}
}

b*b2015-09-01 07:09

3 楼

psudo code:
List> result = new ArrayList<>();
List> inProgress = new ArrayList<>();
inProgress.add(new ArrayList<>(root));
while(!inProgress.isEmpty())
{
List cur = inProgress.remove(0);
if (cur.left == null && cur.right == null)
{
result.add(cur);
continue;
}
if (cur.left != null)
{
List newLeft = new List(cur);
newLeft.add(cur.left);
inProgress.add(newLeft);
}
//do the same for the right
}
return result;

呢？

【在 j**********3 的大作中提到】

: 但是不能用recursion。
: 有人说，用stack, 我百思不得其解，这也不是pre/in order traverse, 咋用stack呢？
: 我想了一个办法，还是用queue，但是每个node换一个新class，带个parent。
: 可是这样就要造一个新class。
: 有什么办法还用原来的treenode么？

b*b2015-09-01 07:09

4 楼

ha, BFS and DFS, lol

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

: psudo code:
: List> result = new ArrayList<>();
: List> inProgress = new ArrayList<>();
: inProgress.add(new ArrayList<>(root));
: while(!inProgress.isEmpty())
: {
: List cur = inProgress.remove(0);
: if (cur.left == null && cur.right == null)
: {
: result.add(cur);

p*22015-09-01 07:09

5 楼

呢？
post order行吗？用一个list模拟stack。这样可以从list直接打印结果。

【在 j**********3 的大作中提到】

l*s2015-09-01 07:09

6 楼

两个Queue也可以吧，Queue 和 Queue，保持两个Queue同步就行了
。
It's accepted by leetcode.
private IList allPath(TreeNode root){
Queue queue = new Queue();
Queue qStr = new Queue();
IList result = new List();
if(root == null) return result;
queue.Enqueue(root); qStr.Enqueue(root.val.ToString());
while(queue.Count != 0){
TreeNode cur = queue.Dequeue();
string curStr = qStr.Dequeue();
if(cur.left == null && cur.right == null) result.Add(curStr);
if(cur.left != null){
queue.Enqueue(cur.left);
qStr.Enqueue(curStr + "->" + cur.left.val);
}
if(cur.right != null){
queue.Enqueue(cur.right);
qStr.Enqueue(curStr + "->" + cur.right.val);
}
}
return result;
}

j*32015-09-01 07:09

7 楼

why post order

【在 p*****2 的大作中提到】

:
: 呢？
: post order行吗？用一个list模拟stack。这样可以从list直接打印结果。

j*32015-09-01 07:09

8 楼

that's more space. how to do it with less space?

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

: 两个Queue也可以吧，Queue 和 Queue，保持两个Queue同步就行了
: 。
: It's accepted by leetcode.
: private IList allPath(TreeNode root){
: Queue queue = new Queue();
: Queue qStr = new Queue();
: IList result = new List();
: if(root == null) return result;
: queue.Enqueue(root); qStr.Enqueue(root.val.ToString());
: while(queue.Count != 0){

l*s2015-09-01 07:09

9 楼

没有很多space，因为中间过程并没有比结果更多使用space。唯一的concern是
treenode那个queue，不过你似乎也是要必用的，这个也不是问题，除非你不用bfs。

【在 j**********3 的大作中提到】

: that's more space. how to do it with less space?

k*r2015-09-01 07:09

10 楼

which language it is?

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

l*s2015-09-01 07:09

11 楼

C#

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

: which language it is?

k*r2015-09-01 07:09

12 楼

nice one!
Iooks like java :)

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

: C#

I*g2015-09-01 07:09

13 楼

确实是：
qStr有很多重复，这样，space 明显增多。
leetcode 没有detect。

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

: 没有很多space，因为中间过程并没有比结果更多使用space。唯一的concern是
: treenode那个queue，不过你似乎也是要必用的，这个也不是问题，除非你不用bfs。

j*32015-09-01 07:09

14 楼

so what is the best solution for this problem?

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

: 确实是：
: qStr有很多重复，这样，space 明显增多。
: leetcode 没有detect。

I*g2015-09-01 07:09

15 楼

用stack做 backtrack 是最好的方法，

【在 j**********3 的大作中提到】

: so what is the best solution for this problem?

d*e2015-09-01 07:09

16 楼

这个用经典的stack backtrack
第一次进入标记并加入path stack
第二次弹出
用两个stack

【在 j**********3 的大作中提到】

: so what is the best solution for this problem?

j*32015-09-01 07:09

17 楼

请具体说说，我看到有人说stack，但不知道咋做。。。

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

: 用stack做 backtrack 是最好的方法，

p*g2015-09-01 07:09

18 楼

如果再定义一个类，里面包含一个状态位和一个树节点。
入栈，出栈都是对这个新的类来操作。
如果是这样，就很容易实现。不加状态位就感觉很麻烦。
坐等大牛来解答。

【在 j**********3 的大作中提到】

: 请具体说说，我看到有人说stack，但不知道咋做。。。

g*e2015-09-01 07:09

19 楼

recursion不就是build stack吗？
[在 jobhunter123 (jobhunting) 的大作中提到：]
：但是不能用recursion。
：
：...........