遍历二叉树除了recursion还有啥好办法？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

遍历二叉树除了recursion还有啥好办法？

遍历二叉树除了recursion还有啥好办法？# JobHunting - 待字闺中

W*o2014-12-12 08:12

1 楼

今天给了一个recursion的解法，然后又让我用stack做，我当时萌了，大家说说stack
咋解？

f*i2014-12-12 08:12

2 楼

标准dfs遍历，也可以用queue做标准bfs遍历，这些都是基础，建议楼主多做点题

stack

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

: 今天给了一个recursion的解法，然后又让我用stack做，我当时萌了，大家说说stack
: 咋解？

p*t2014-12-12 08:12

3 楼

取决于你哪种遍历方法
后序最麻烦先序最简单

stack

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

: 今天给了一个recursion的解法，然后又让我用stack做，我当时萌了，大家说说stack
: 咋解？

p*t2014-12-12 08:12

4 楼

不会用栈遍历二叉树的你让他用栈做DFS不是更不会。。。

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

: 标准dfs遍历，也可以用queue做标准bfs遍历，这些都是基础，建议楼主多做点题
:
: stack

p*t2014-12-12 08:12

5 楼

举个先序的例子给你吧
while(current != NULL || !stack.empty()){
if(current != NULL){
stack.push(current);
visit(current);
current = current -> left;
}
else{
current = stack.top();
stack.pop();
current = current -> right;
}
}
中序的其实很类似访问current的时间变一下而已

stack

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

: 今天给了一个recursion的解法，然后又让我用stack做，我当时萌了，大家说说stack
: 咋解？

w*k2014-12-12 08:12

6 楼

后序用两个堆栈来解那是相当容易，不到10行代码。

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

: 取决于你哪种遍历方法
: 后序最麻烦先序最简单
:
: stack

w*a2014-12-12 08:12

7 楼

后续可以当先序做，push的时候先左后右，最后reverse一下，也简单

g*02014-12-12 08:12

8 楼

递归不就是用栈实现的么，把传入递归函数的参数压栈即可。

stack

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

: 今天给了一个recursion的解法，然后又让我用stack做，我当时萌了，大家说说stack
: 咋解？

W*o2014-12-12 08:12

9 楼

谢谢，
我去之前是毫无准备，以为不会考算法；就这recursive解法我还是吃老本的，呵呵

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

: 举个先序的例子给你吧
: while(current != NULL || !stack.empty()){
: if(current != NULL){
: stack.push(current);
: visit(current);
: current = current -> left;
: }
: else{
: current = stack.top();
: stack.pop();