求问把二叉树的recursive遍历改为stack实现的思路# JobHunting - 待字闺中d*o2013-03-27 07:031 楼以preorder为例我知道recursive的该怎么写,也知道stack的方法该怎么写但是我不知道是怎么能从recursive的方法看出来stack的应该这么写求问这个思考的过程多谢!
c*r2013-03-27 07:033 楼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*o2013-03-27 07:034 楼我是知道这么写但是不知道这个是怎么得出来的从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*h2013-03-27 07:035 楼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*o2013-03-27 07:036 楼没有人谈谈思路吗?我要的不是code啊,code我自己也会写难道大家也是看到书上这么写,验证是对的以后然后背下来了?那以后遇到一个不同的情况,recursive的一个什么函数,让你用stack替换成非recursive的,怎么下手呢?
f*s2013-03-27 07:037 楼这个??是不是要先压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*o2013-03-27 07:038 楼是的,应该先push right这样pop的时候才能先pop出left【在 f****s 的大作中提到】: 这个??: 是不是要先压right再压left啊?
d*32013-03-27 07:039 楼你这个先序对么?试试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*s2013-03-27 07:0310 楼有个不需要的版本,顺便再练一遍。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*s2013-03-27 07:0311 楼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*42013-03-27 07:0312 楼recursive本身就是压栈啊从进入一个函数开始,就开始压栈。。有变量压变量,有函数压函数。。你这么想,你先遇到root node。。这个要压栈吧然后你是不是call这个function,但是传left node。。进入这个函数,是不是又要压栈,这不就是压的新的root就是left node。。,然后是这个left node 的leftnode 等等等等。直到没有,这时候你pop了一个。。因为有一个有返回值了,可以去下一行了。。但你很快发现你遇到了call rightnode的那个function,。。。所以对这个function,你又开始做一遍和上面同样的事情。。。看不懂就当我在胡言乱语吧。。
b*l2013-03-27 07:0313 楼一开始的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*e2013-03-27 07:0314 楼看懂了,谢谢!【在 f********4 的大作中提到】: recursive本身就是压栈啊: 从进入一个函数开始,就开始压栈。。: 有变量压变量,有函数压函数。。: 你这么想,你先遇到root node。。这个要压栈吧: 然后你是不是call这个function,但是传left node。。: 进入这个函数,是不是又要压栈,这不就是压的新的root就是left node。。,然后是: 这个left node 的leftnode 等等等等。直到没有,这时候你pop了一个。。因为有一个: 有返回值了,可以去下一行了。。但你很快发现你遇到了call rightnode的那个: function,。。。所以对这个function,你又开始做一遍和上面同样的事情。。。看不: 懂就当我在胡言乱语吧。。