d**********o
发帖数: 11 | 1 以preorder为例
我知道recursive的该怎么写，也知道stack的方法该怎么写
但是我不知道是怎么能从recursive的方法看出来stack的应该这么写
求问这个思考的过程
多谢！ |
r**h
发帖数: 1288 | 2 我猜lz想问的是二叉树使用stack/循环的pre-order traversal的实现？ |
c*******r
发帖数: 309 | 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的方法 |
d**********o
发帖数: 11 | 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);
|
r**h
发帖数: 1288 | 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);
|
d**********o
发帖数: 11 | 6 没有人谈谈思路吗？
我要的不是code啊，code我自己也会写
难道大家也是看到书上这么写，验证是对的以后然后背下来了？
那以后遇到一个不同的情况，recursive的一个什么函数，让你用stack替换成非
recursive的，怎么下手呢？ |
f****s
发帖数: 74 | 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);
|
d**********o
发帖数: 11 | 8 是的，应该先push right
这样pop的时候才能先pop出left
【在 f****s 的大作中提到】
: 这个??
: 是不是要先压right再压left啊？
|
d*******3
发帖数: 58 | 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);
|
f****s
发帖数: 74 | 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);
|
f****s
发帖数: 74 | 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
|
f********4
发帖数: 988 | 12 recursive本身就是压栈啊
从进入一个函数开始，就开始压栈。。
有变量压变量，有函数压函数。。
你这么想，你先遇到root node。。这个要压栈吧
然后你是不是call这个function，但是传left node。。
进入这个函数，是不是又要压栈，这不就是压的新的root就是left node。。，然后是
这个left node 的leftnode 等等等等。直到没有，这时候你pop了一个。。因为有一个
有返回值了，可以去下一行了。。但你很快发现你遇到了call rightnode的那个
function，。。。所以对这个function，你又开始做一遍和上面同样的事情。。。看不
懂就当我在胡言乱语吧。。 |
b*******l
发帖数: 590 | 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;
|
e****e
发帖数: 418 | 14 看懂了，谢谢！
【在 f********4 的大作中提到】
: recursive本身就是压栈啊
: 从进入一个函数开始，就开始压栈。。
: 有变量压变量，有函数压函数。。
: 你这么想，你先遇到root node。。这个要压栈吧
: 然后你是不是call这个function，但是传left node。。
: 进入这个函数，是不是又要压栈，这不就是压的新的root就是left node。。，然后是
: 这个left node 的leftnode 等等等等。直到没有，这时候你pop了一个。。因为有一个
: 有返回值了，可以去下一行了。。但你很快发现你遇到了call rightnode的那个
: function，。。。所以对这个function，你又开始做一遍和上面同样的事情。。。看不
: 懂就当我在胡言乱语吧。。
|
