S**Y
发帖数: 136 | 1 plz implement a non-recursive post order tree traversal.
I think this is difficult. It is kinda simple for pre-order and in-order, bu
t post-order is tough. |
r****o
发帖数: 1950 | 2 why post-order is tough?
bu
【在 S**Y 的大作中提到】
: plz implement a non-recursive post order tree traversal.
: I think this is difficult. It is kinda simple for pre-order and in-order, bu
: t post-order is tough.
|
S**Y
发帖数: 136 | 3 code it :)
【在 r****o 的大作中提到】
: why post-order is tough?
:
: bu
|
f*********r
发帖数: 68 | 4 use standard techniques to convert the recursive function to non-recursive
function. almost same as in and pre orders.
void postOrder() {
Node *p = root, *pre = root;
stack st;
int i = 0;
while(!st.empty() || p){
while(p){
st.push(p);
p = p->left;
}
p = st.top();
if(p->right == NULL || p->right == pre) {
visit(p);
st.pop();
pre = p;
p = NULL;
}
else
【在 S**Y 的大作中提到】
: plz implement a non-recursive post order tree traversal.
: I think this is difficult. It is kinda simple for pre-order and in-order, bu
: t post-order is tough.
|
S**Y
发帖数: 136 | 5 cool.you are so fast.
could you give more hint(or a link/book) about "standard techniques to conve
rt the recursive func to non-recursive func."?
It cost me much time and brain to convert it myself.. thanks a lot.
【在 f*********r 的大作中提到】
: use standard techniques to convert the recursive function to non-recursive
: function. almost same as in and pre orders.
: void postOrder() {
: Node *p = root, *pre = root;
: stack st;
: int i = 0;
: while(!st.empty() || p){
: while(p){
: st.push(p);
: p = p->left;
|
f*********r
发帖数: 68 | 6 you will find those kind of techniques in the book "Algorithms in C", author
conve |
g*******y
发帖数: 1930 | 7 我这个不用stack，queue这些
貌似有的面试可能会有这个要求。
while(root->left || root->right){
if (root->left){
root = root->left;
}else{
root = root->right;
}
}
do{
print(root);
if( root = root->p->left){
if(root->p->right){
root = root->p->right;
}else{
root = root->p;
}
}else{
root = root->p;
}
}while(root->p) |
S**Y
发帖数: 136 | 8 but u r changing the Node data structure?
【在 g*******y 的大作中提到】
: 我这个不用stack，queue这些
: 貌似有的面试可能会有这个要求。
: while(root->left || root->right){
: if (root->left){
: root = root->left;
: }else{
: root = root->right;
: }
: }
: do{
|
g*******y
发帖数: 1930 | 9 树的data structure中，link to parent 还是很常见吧
再说了，总得花额外的空间。
我只是假设面试的人要求不能用stack/queue但是有node->p的话，这个比用stack什么的，难度稍微增加一点点。其实时间和空间差不多的。如果你要考虑stack可能会resize什么的话，我这个还好些。
【在 S**Y 的大作中提到】
: but u r changing the Node data structure?
|
f*********r
发帖数: 68 | 10 I don't think it's possible for standard tree structure.
【在 g*******y 的大作中提到】
: 我这个不用stack，queue这些
: 貌似有的面试可能会有这个要求。
: while(root->left || root->right){
: if (root->left){
: root = root->left;
: }else{
: root = root->right;
: }
: }
: do{
|
|
|
g*******y
发帖数: 1930 | 11 come on, we are talking about interview prob, interviewer can have any version
of tree he wants, to make the problem slightly harder.
【在 f*********r 的大作中提到】
: I don't think it's possible for standard tree structure.
|
g*******y
发帖数: 1930 | 12 yes I agree.
stack size is h
it's the queue for BFS that costs O(N);
【在 f*********r 的大作中提到】
: I don't think it's possible for standard tree structure.
|
f*********r
发帖数: 68 | 13 I also think if you have pointer to parent in the tree structure, most of
the tree problems will become easier.
【在 g*******y 的大作中提到】
: yes I agree.
: stack size is h
: it's the queue for BFS that costs O(N);
|
f*********r
发帖数: 68 | 14 just like the problems for the doubly linked list is much easier than the
same problem for the singly linked list.
【在 f*********r 的大作中提到】
: I also think if you have pointer to parent in the tree structure, most of
: the tree problems will become easier.
|
S**Y
发帖数: 136 | 15 just found the book you mentioned.thanks.
it is very comprehensive book, my first impression..hehe
【在 f*********r 的大作中提到】
: just like the problems for the doubly linked list is much easier than the
: same problem for the singly linked list.
|
f*********r
发帖数: 68 | 16 动作真快~.
【在 S**Y 的大作中提到】
: just found the book you mentioned.thanks.
: it is very comprehensive book, my first impression..hehe
|
S**Y
发帖数: 136 | |
g*******y
发帖数: 1930 | 18 insteresting idea...
any example tree problem in your mind? I think I've done too few problems
to see a really difficult one.
if most tree problems will become easier with parent link, why don't they
just have one? hehe
【在 f*********r 的大作中提到】
: I also think if you have pointer to parent in the tree structure, most of
: the tree problems will become easier.
|
f*********r
发帖数: 68 | 19 en, you are right~
【在 g*******y 的大作中提到】
: insteresting idea...
: any example tree problem in your mind? I think I've done too few problems
: to see a really difficult one.
: if most tree problems will become easier with parent link, why don't they
: just have one? hehe
|
g*******y
发帖数: 1930 | 20 by the way, your code seems not working
【在 f*********r 的大作中提到】
: use standard techniques to convert the recursive function to non-recursive
: function. almost same as in and pre orders.
: void postOrder() {
: Node *p = root, *pre = root;
: stack st;
: int i = 0;
: while(!st.empty() || p){
: while(p){
: st.push(p);
: p = p->left;
|
|
|
f*********r
发帖数: 68 | 21 maybe not right, I didn't test it. watching movie now
【在 g*******y 的大作中提到】
: by the way, your code seems not working
|
g*******y
发帖数: 1930 | 22 我改了一下:
void findNext(Node *node, stack &stk)){
while(node->left || node->right){
stk.push(node);
node = (node->left)? node->left : node->right;
}
stk.push(node);
}
void post2(Node *root){
if(!root) return;
stack stk;
Node *node, *pre;
findNext(root,stk);
pre = stk.top(); visit(pre); stk.pop();
while(!stk.empty()){
node = stk.top();
if(node->right==0 || node->right == pre){
visit(node); stk.pop(); pre =
【在 f*********r 的大作中提到】
: maybe not right, I didn't test it. watching movie now
|
s*******e
发帖数: 174 | 23 public void postOrderTraversal(TreeNode root)
{
Stack s = new Stack();
s.push(root);
while(!s.isEmpty())
{
TreeNode node = (TreeNode)s.peek();
if(node.left != null && !node.left.visited)
s.push(node.left);
else if(node.right != null && !node.right.visited)
s.push(node.right);
else
{
System.out.print(node.value+" ");
node.visited = true;
s.pop();
}
}
|
s*******e
发帖数: 174 | 24 en, just tested, it worked.. |
g*******y
发帖数: 1930 | 25 你用了 .visited ，简化了问题
【在 s*******e 的大作中提到】
: public void postOrderTraversal(TreeNode root)
: {
: Stack s = new Stack();
: s.push(root);
: while(!s.isEmpty())
: {
: TreeNode node = (TreeNode)s.peek();
: if(node.left != null && !node.left.visited)
: s.push(node.left);
: else if(node.right != null && !node.right.visited)
|
S**Y
发帖数: 136 | 26 ft..
it is really confusing to look at people's code without comments
Can u comment it?
【在 g*******y 的大作中提到】
: 我改了一下:
: void findNext(Node *node, stack &stk)){
: while(node->left || node->right){
: stk.push(node);
: node = (node->left)? node->left : node->right;
: }
: stk.push(node);
: }
: void post2(Node *root){
: if(!root) return;
|
g*******y
发帖数: 1930 | 27 void FindLeftmostLeaf(Node *root, stack &stk){
while(root->left || root->right){ //while(当前节点不是叶子)
stk.push(root);
if (root->left){
root = root->left;
}else{
root = root->right;
}
}
stk.push(root);
}
void PostOrder(Node *root){
if(root) return; //check empty tree;
stack stk;
Node *node=root, *parent;
//找子树中最左边的叶子，并把途中的节点放入栈
FindLeftmostLeaf(root,stk);
while(!stk.empty()){
node
【在 S**Y 的大作中提到】
: ft..
: it is really confusing to look at people's code without comments
: Can u comment it?
|
c*****e
发帖数: 210 | 28 void tranverse(node *root){
vector stack;
node *p;
node *np;
stack.push_back(root);
while(stack.size()>0){
p=stack.back();
if(p->left==NULL&&p->right==NULL)
cout<data;//只有terminal 节点才被输出
else{
stack.pop_back();
np=new node;//把visit过的节点copy成terminal, 以后再输出
np->left=np->right=NULL;
np->data=p.data;
stack.push_pack(np);
}
if(p->right!=NULL)
stack.push_pack(p->right);
if(p->left!=NULL)
stack.push_pack(p->le |
g*******y
发帖数: 1930 | 29 嗯，比较简洁。不过代价是你得复制一次data，这个就得考虑data的大小了，而且还有
不少限制，比如data的type是否允许copy，或者visit不一定是只读的过程。。。
【在 c*****e 的大作中提到】
: void tranverse(node *root){
: vector stack;
: node *p;
: node *np;
: stack.push_back(root);
: while(stack.size()>0){
: p=stack.back();
: if(p->left==NULL&&p->right==NULL)
: cout<data;//只有terminal 节点才被输出
: else{
|
C**********n
发帖数: 100 | 30 老大你太牛了，
能说说思路吗？
我看明白了但是还是觉得挺难的。
【在 g*******y 的大作中提到】
: void FindLeftmostLeaf(Node *root, stack &stk){
: while(root->left || root->right){ //while(当前节点不是叶子)
: stk.push(root);
: if (root->left){
: root = root->left;
: }else{
: root = root->right;
: }
: }
: stk.push(root);
|
|
|
h******i
发帖数: 5 | 31 possible error: if(!stk.empty()) return;
should be
if(stk.empty()) return;
【在 g*******y 的大作中提到】
: void FindLeftmostLeaf(Node *root, stack &stk){
: while(root->left || root->right){ //while(当前节点不是叶子)
: stk.push(root);
: if (root->left){
: root = root->left;
: }else{
: root = root->right;
: }
: }
: stk.push(root);
|
g*******y
发帖数: 1930 | 32 haha,my shame~
【在 h******i 的大作中提到】
: possible error: if(!stk.empty()) return;
: should be
: if(stk.empty()) return;
|
C**********n
发帖数: 100 | 33 hehe, 还有if (root) return -> if (!root) return
能说说解这种题的思路吗？
【在 g*******y 的大作中提到】
: haha,my shame~
|
g*******y
发帖数: 1930 | 34 sigh...too many careless flaws...
思路其实跟我前面发的那个code，不用stack，但是假设每个node都有个parent link。
这个用stack的版本，只不过就是用stack记录了必要的一串parent而已。
另外一个想法是，假设我现在的stack里面有一堆正确的，必要的元素了，并且top的那
个就是当前需要visit的。那么在visit它后，应该做什么？加入新的元素并始终保持最
top的那个element in stack是当前需要visit的node? 或者pop掉? pop掉后，stack里
面next的元素应该是什么。
【在 C**********n 的大作中提到】
: hehe, 还有if (root) return -> if (!root) return
: 能说说解这种题的思路吗？
|
h******i
发帖数: 5 | 35 暇不掩玉，
牛人，赞一下！
【在 g*******y 的大作中提到】
: haha,my shame~
|
S**Y
发帖数: 136 | 36 your first version doesn't work. :)
but i like your second version very much, which makes it very straightforwar
d by using the FindNextEle function.
【在 g*******y 的大作中提到】
: sigh...too many careless flaws...
: 思路其实跟我前面发的那个code，不用stack，但是假设每个node都有个parent link。
: 这个用stack的版本，只不过就是用stack记录了必要的一串parent而已。
: 另外一个想法是，假设我现在的stack里面有一堆正确的，必要的元素了，并且top的那
: 个就是当前需要visit的。那么在visit它后，应该做什么？加入新的元素并始终保持最
: top的那个element in stack是当前需要visit的node? 或者pop掉? pop掉后，stack里
: 面next的元素应该是什么。
|
g*******y
发帖数: 1930 | 37 呵呵，谢谢指出。不过我昨天也看到这个错误了，只是在自己电脑上改了，不过没有post出来。既然有人指出来，呵呵，我就Post一下吧。省略掉了判断empty啊，是不是null指针等细节。可以看出来，这个用Parent指针的方法，跟用stack的版本非常的相似。
void nextPost(Node *&root){ //还是找最左的叶子
while(root->left || root->right){
if (root->left){
root = root->left;
}else{
root = root->right;
}
}
}
void post_traversal(Node *root){
nextPost(root); //图简便，省去trival的判断了，直接找最左叶子
while(root->p){ //while不是根节点
visit(root);
if( root == root->p->left){ /
【在 S**Y 的大作中提到】
: your first version doesn't work. :)
: but i like your second version very much, which makes it very straightforwar
: d by using the FindNextEle function.
|
