求问把二叉树的recursive遍历改为stack实现的思路# JobHunting - 待字闺中
d*o
1 楼
以preorder为例
我知道recursive的该怎么写，也知道stack的方法该怎么写
但是我不知道是怎么能从recursive的方法看出来stack的应该这么写
求问这个思考的过程
多谢！
我知道recursive的该怎么写，也知道stack的方法该怎么写
但是我不知道是怎么能从recursive的方法看出来stack的应该这么写
求问这个思考的过程
多谢！
r*h
2 楼
我猜lz想问的是二叉树使用stack/循环的pre-order traversal的实现？
c*r
3 楼
public void preOrderTraversal(Node root){
if(root==null)
return null;
Stack stack=new Stack();
stack.push(root);
while(!stack.isEmpty()){
Node temp=stack.pop();
System.out.println(temp.val);
if(temp.left!=null)
stack.push(temp.left);
if(temp.right!=null)
stack.push(temp.right);
}
}
比较麻烦的是inOrderTraversal. 需要写一个pushLeft的方法
if(root==null)
return null;
Stack
stack.push(root);
while(!stack.isEmpty()){
Node temp=stack.pop();
System.out.println(temp.val);
if(temp.left!=null)
stack.push(temp.left);
if(temp.right!=null)
stack.push(temp.right);
}
}
比较麻烦的是inOrderTraversal. 需要写一个pushLeft的方法
d*o
4 楼
我是知道这么写
但是不知道这个是怎么得出来的
从recursive的程序出发，怎么得出这个
【在 c*******r 的大作中提到】
: public void preOrderTraversal(Node root){
: if(root==null)
: return null;
: Stack stack=new Stack();
: stack.push(root);
: while(!stack.isEmpty()){
: Node temp=stack.pop();
: System.out.println(temp.val);
: if(temp.left!=null)
: stack.push(temp.left);
但是不知道这个是怎么得出来的
从recursive的程序出发，怎么得出这个
【在 c*******r 的大作中提到】
: public void preOrderTraversal(Node root){
: if(root==null)
: return null;
: Stack
: stack.push(root);
: while(!stack.isEmpty()){
: Node temp=stack.pop();
: System.out.println(temp.val);
: if(temp.left!=null)
: stack.push(temp.left);
r*h
5 楼
in order和pre order基本上一样
真正麻烦的是post order
【在 c*******r 的大作中提到】
: public void preOrderTraversal(Node root){
: if(root==null)
: return null;
: Stack stack=new Stack();
: stack.push(root);
: while(!stack.isEmpty()){
: Node temp=stack.pop();
: System.out.println(temp.val);
: if(temp.left!=null)
: stack.push(temp.left);
真正麻烦的是post order
【在 c*******r 的大作中提到】
: public void preOrderTraversal(Node root){
: if(root==null)
: return null;
: Stack
: stack.push(root);
: while(!stack.isEmpty()){
: Node temp=stack.pop();
: System.out.println(temp.val);
: if(temp.left!=null)
: stack.push(temp.left);
d*o
6 楼
没有人谈谈思路吗？
我要的不是code啊，code我自己也会写
难道大家也是看到书上这么写，验证是对的以后然后背下来了？
那以后遇到一个不同的情况，recursive的一个什么函数，让你用stack替换成非
recursive的，怎么下手呢？
我要的不是code啊，code我自己也会写
难道大家也是看到书上这么写，验证是对的以后然后背下来了？
那以后遇到一个不同的情况，recursive的一个什么函数，让你用stack替换成非
recursive的，怎么下手呢？
f*s
7 楼
这个??
是不是要先压right再压left啊？
【在 c*******r 的大作中提到】
: public void preOrderTraversal(Node root){
: if(root==null)
: return null;
: Stack stack=new Stack();
: stack.push(root);
: while(!stack.isEmpty()){
: Node temp=stack.pop();
: System.out.println(temp.val);
: if(temp.left!=null)
: stack.push(temp.left);
是不是要先压right再压left啊？
【在 c*******r 的大作中提到】
: public void preOrderTraversal(Node root){
: if(root==null)
: return null;
: Stack
: stack.push(root);
: while(!stack.isEmpty()){
: Node temp=stack.pop();
: System.out.println(temp.val);
: if(temp.left!=null)
: stack.push(temp.left);
d*o
8 楼
是的，应该先push right
这样pop的时候才能先pop出left
【在 f****s 的大作中提到】
: 这个??
: 是不是要先压right再压left啊？
这样pop的时候才能先pop出left
【在 f****s 的大作中提到】
: 这个??
: 是不是要先压right再压left啊？
d*3
9 楼
你这个先序对么？试试
1
/ \
2 3
【在 c*******r 的大作中提到】
: public void preOrderTraversal(Node root){
: if(root==null)
: return null;
: Stack stack=new Stack();
: stack.push(root);
: while(!stack.isEmpty()){
: Node temp=stack.pop();
: System.out.println(temp.val);
: if(temp.left!=null)
: stack.push(temp.left);
1
/ \
2 3
【在 c*******r 的大作中提到】
: public void preOrderTraversal(Node root){
: if(root==null)
: return null;
: Stack
: stack.push(root);
: while(!stack.isEmpty()){
: Node temp=stack.pop();
: System.out.println(temp.val);
: if(temp.left!=null)
: stack.push(temp.left);
f*s
10 楼
有个不需要的版本，顺便再练一遍。
void inorder(Node* root){
if(!root)
return;
stack s;
Node* cur=root;
while(1){
while(cur){
s.push(cur);
cur=cur->left;
}
if(s.empty())
break;
cout<val;
s.pop();
cur=cur->right;
}
}
【在 c*******r 的大作中提到】
: public void preOrderTraversal(Node root){
: if(root==null)
: return null;
: Stack stack=new Stack();
: stack.push(root);
: while(!stack.isEmpty()){
: Node temp=stack.pop();
: System.out.println(temp.val);
: if(temp.left!=null)
: stack.push(temp.left);
void inorder(Node* root){
if(!root)
return;
stack
Node* cur=root;
while(1){
while(cur){
s.push(cur);
cur=cur->left;
}
if(s.empty())
break;
cout<
s.pop();
cur=cur->right;
}
}
【在 c*******r 的大作中提到】
: public void preOrderTraversal(Node root){
: if(root==null)
: return null;
: Stack
: stack.push(root);
: while(!stack.isEmpty()){
: Node temp=stack.pop();
: System.out.println(temp.val);
: if(temp.left!=null)
: stack.push(temp.left);
f*s
11 楼
leetcode上给出的思想很好。就是keep一个pre和一个cur，
如果cur是pre的孩子，说明我们正从上到下，如果反过来，说明我们从下往上，就该打
印节点了。
顺便练一个，
void postorder(Node* r)
{
if(!r) return;
stack s;
Node* pre=0;
Node* cur=r;
s.push(r);
while(!s.empty()){
cur=s.top();
if(pre==0||cur==pre->left||cur==pre->right){
if(cur->left) s.push(cur->left);
else if(cur->right) s.push(cur->right);
else{
cout<val;
s.pop();
}
}else{
if(pre=cur->left){
if(cur->right) s.push(cur->right);
else{
cout<val;
s.pop();
}
}else if(pre=cur->right){
cout<val;
s.pop()
}
}
pre=cur;
}
}
【在 r**h 的大作中提到】
: in order和pre order基本上一样
: 真正麻烦的是post order
如果cur是pre的孩子，说明我们正从上到下，如果反过来，说明我们从下往上，就该打
印节点了。
顺便练一个，
void postorder(Node* r)
{
if(!r) return;
stack
Node* pre=0;
Node* cur=r;
s.push(r);
while(!s.empty()){
cur=s.top();
if(pre==0||cur==pre->left||cur==pre->right){
if(cur->left) s.push(cur->left);
else if(cur->right) s.push(cur->right);
else{
cout<
s.pop();
}
}else{
if(pre=cur->left){
if(cur->right) s.push(cur->right);
else{
cout<
s.pop();
}
}else if(pre=cur->right){
cout<
s.pop()
}
}
pre=cur;
}
}
【在 r**h 的大作中提到】
: in order和pre order基本上一样
: 真正麻烦的是post order
f*4
12 楼
recursive本身就是压栈啊
从进入一个函数开始，就开始压栈。。
有变量压变量，有函数压函数。。
你这么想，你先遇到root node。。这个要压栈吧
然后你是不是call这个function，但是传left node。。
进入这个函数，是不是又要压栈，这不就是压的新的root就是left node。。，然后是
这个left node 的leftnode 等等等等。直到没有，这时候你pop了一个。。因为有一个
有返回值了，可以去下一行了。。但你很快发现你遇到了call rightnode的那个
function，。。。所以对这个function，你又开始做一遍和上面同样的事情。。。看不
懂就当我在胡言乱语吧。。
从进入一个函数开始，就开始压栈。。
有变量压变量，有函数压函数。。
你这么想，你先遇到root node。。这个要压栈吧
然后你是不是call这个function，但是传left node。。
进入这个函数，是不是又要压栈，这不就是压的新的root就是left node。。，然后是
这个left node 的leftnode 等等等等。直到没有，这时候你pop了一个。。因为有一个
有返回值了，可以去下一行了。。但你很快发现你遇到了call rightnode的那个
function，。。。所以对这个function，你又开始做一遍和上面同样的事情。。。看不
懂就当我在胡言乱语吧。。
b*l
13 楼
一开始的
if(!root)
return;
我觉得好像不需要。
【在 f****s 的大作中提到】
: 有个不需要的版本，顺便再练一遍。
: void inorder(Node* root){
: if(!root)
: return;
: stack s;
: Node* cur=root;
: while(1){
: while(cur){
: s.push(cur);
: cur=cur->left;
if(!root)
return;
我觉得好像不需要。
【在 f****s 的大作中提到】
: 有个不需要的版本，顺便再练一遍。
: void inorder(Node* root){
: if(!root)
: return;
: stack
: Node* cur=root;
: while(1){
: while(cur){
: s.push(cur);
: cur=cur->left;
e*e
14 楼
看懂了，谢谢！
【在 f********4 的大作中提到】
: recursive本身就是压栈啊
: 从进入一个函数开始，就开始压栈。。
: 有变量压变量，有函数压函数。。
: 你这么想，你先遇到root node。。这个要压栈吧
: 然后你是不是call这个function，但是传left node。。
: 进入这个函数，是不是又要压栈，这不就是压的新的root就是left node。。，然后是
: 这个left node 的leftnode 等等等等。直到没有，这时候你pop了一个。。因为有一个
: 有返回值了，可以去下一行了。。但你很快发现你遇到了call rightnode的那个
: function，。。。所以对这个function，你又开始做一遍和上面同样的事情。。。看不
: 懂就当我在胡言乱语吧。。
【在 f********4 的大作中提到】
: recursive本身就是压栈啊
: 从进入一个函数开始，就开始压栈。。
: 有变量压变量，有函数压函数。。
: 你这么想，你先遇到root node。。这个要压栈吧
: 然后你是不是call这个function，但是传left node。。
: 进入这个函数，是不是又要压栈，这不就是压的新的root就是left node。。，然后是
: 这个left node 的leftnode 等等等等。直到没有，这时候你pop了一个。。因为有一个
: 有返回值了，可以去下一行了。。但你很快发现你遇到了call rightnode的那个
: function，。。。所以对这个function，你又开始做一遍和上面同样的事情。。。看不
: 懂就当我在胡言乱语吧。。
相关阅读
我的找工作经历 (统计类)找工后遗症面试了几个人，上来说几句。[合集] 回国作faculty 之我见暂时尘埃落定了我的on-site经验 ME Fresh PhD和大家分享我的找工作历程EE的找工作的點點滴滴直播贴//我的求职路我也来谈谈ICC:认清其本性大家去Amazon下单买东西别忘了OCEF...呀 (转载)[合集] 关于cpt->opt->h1b的经验和教训关于negotiate 工资 (zt)【分享】最新出炉的微软面试题[合集] 痛苦折腾了几个月, 总算有些成果答XDJM们的邮件（继我一个半月的找工作经历）USCIS CSC OPT Expedite Handling Request Info直播贴//我的求职路 (2)一道M$面试题的解法...在读CS PhD 找工经历（四）---好为人师