j*****g
发帖数: 223 | 1 不好意思。本来这题飘过，都没有正眼看一下。没想到近来想练练手，楞是没做出来。
pre-order and in-order are easy.
But post order, iterative traversal, without setting flags on the nodes....
how .... //老泪纵横.. |
y*********e
发帖数: 518 | 2 贴一贴代码 ：）
void postorder(const Node* node) {
std::stack stack;
while (node != NULL || !stack.empty()) {
if (node == NULL) {
while (!stack.empty() && node == stack.top()->right) {
node = stack.top(); stack.pop();
process(node->value);
}
node = stack.empty() ? NULL : stack.top()->right;
}
if (node != NULL) {
stack.push(node);
node = node->left;
}
}
} |
j*****g
发帖数: 223 | 3 很玄妙亚。。
specially these lines
"if (node = NULL) { while (!stack.empty() && node == stack.top()->right)"
in some case, when node is NULL, stack.top()->right may not necessarily be
NULL, so the while will come out immediately.
能解释一下整个算法的思路吗? 谢谢!
【在 y*********e 的大作中提到】
: 贴一贴代码 ：）
: void postorder(const Node* node) {
: std::stack stack;
: while (node != NULL || !stack.empty()) {
: if (node == NULL) {
: while (!stack.empty() && node == stack.top()->right) {
: node = stack.top(); stack.pop();
: process(node->value);
: }
: node = stack.empty() ? NULL : stack.top()->right;
|
i**********e
发帖数: 1145 | 4 他贴的代码是正确的。
你说的没错，当node==NULL 的时候，while loop会立即退出。
在遇到这种情况，我们应该看 stack.top()->right，这时候有两种可能性：
a) right 是 NULL: 那么我们应该打印该节点的值。
b) right 不是 NULL: 那我们应该把 right 节点推上 stack，然后继续。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
right)"
【在 j*****g 的大作中提到】
: 很玄妙亚。。
: specially these lines
: "if (node = NULL) { while (!stack.empty() && node == stack.top()->right)"
: in some case, when node is NULL, stack.top()->right may not necessarily be
: NULL, so the while will come out immediately.
: 能解释一下整个算法的思路吗? 谢谢!
|
i**********e
发帖数: 1145 | 5 这题如果可以加visited node就很好做，不然的话真的很不好做。
不加visited node的话，难点就在怎么知道在哪种情况下应该打印节点的值，或者往右
节点走？
主要思路：
当之前的节点由右边上来的时候，我们就应该打印。而之前的节点是从左边上来的话，
那我们就应该走向右节点，然后继续往下走。怎么知道是从右边或者左边上来呢？答案
就是用一个变量来储存之前的节点，然后往上走的时候可以比较之前的节点是不是此节
点(stack的top)的左孩子还是右孩子。post-order你可以保证之前的节点必须是此节点
的左孩子或者右孩子。这是因为你必须把当前值打印了之后才能从stack里pop掉。
当我们往下走的时候，有三种情况：
1）如果左节点存在的话，就把左节点给push上stack。
2）没有左节点的话，就看右节点。如果右节点存在的话，就把右节点push上stack。
3）如果这是叶子（意味着左右节点都没有），就打印此节点，然后把stack pop掉一个
。记录之前的节点为此节点，然后设为往上走。
当往上走的时候：
1）如果之前节点是此节点的左孩子（从左边上来），那就把右边节点push上stack。然
后设为往下走。
2）如果之前节点是此节点的右孩子（从右边上来），那就打印此节点，然后pop。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
i**********e
发帖数: 1145 | 6 这是我的代码，虽然没有那么漂亮简洁，但是比较容易懂。
我可以尝试把代码缩短，但是缩短之后就很难理解了。
void post_order_traversal_iterative(BinaryTree* root) {
bool down = true;
BinaryTree *prev;
stack s;
s.push(root);
while (!s.empty()) {
BinaryTree *curr = s.top();
if (down) {
if (curr->left) {
s.push(curr->left);
} else {
if (curr->right) {
s.push(curr->right);
} else {
down = false;
cout << curr->data << " ";
s.pop();
prev = curr;
}
}
} else {
if (prev == curr->left) {
down = true;
if (curr->right) {
s.push(curr->right);
} else {
down = false;
cout << curr->data << " ";
s.pop();
prev = curr;
}
} else if (prev == curr->right) {
down = false;
cout << curr->data << " ";
s.pop();
prev = curr;
} else {
cout << "ERROR!\n";
}
}
}
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
c***2
发帖数: 838 | 7 void tree_postorder_traversal_no_recursion (tree_node_type *root)
{
Element *top=NULL, *node, *tmp;
tree_node_type *current_node=root;
if (!root)
return;
/* push current_node into stack */
node=(Element *)malloc(sizeof(Element));
memset(node,0,sizeof(Element));
node->tree_node_ptr=current_node;
top=stack_push(top,node);
while(top) {
/* peek stack */
current_node=top->tree_node_ptr;
/* push current_node->left into stack if it's not visited */
if(current_node->left && !current_node->left->visited){
node=(Element *)malloc(sizeof(Element));
memset(node,0,sizeof(Element));
node->tree_node_ptr=current_node->left;
top=stack_push(top,node);
}
/* push current_node->right into stack if it's not visited */
else if (current_node->right && !current_node->right->visited){
node=(Element *)malloc(sizeof(Element));
memset(node,0,sizeof(Element));
node->tree_node_ptr=current_node->right;
top=stack_push(top,node);
}
else {
/* Visit current_node and mark it */
printf("%d ",current_node->object->data);
current_node->visited=TRUE;
/* pop out one and discard it */
top=stack_pop(top,&tmp);
if(tmp){
free(tmp);
}
else /* stack is empty now */
break;
} /* else */
} /* while */
} |
i**********e
发帖数: 1145 | 8 再试试这个更简洁的思路，去除了使用down的变量。
void post_order_traversal_iterative3(BinaryTree* root) {
stack s;
s.push(root);
BinaryTree *prev = NULL;
while (!s.empty()) {
BinaryTree *curr = s.top();
if (curr->left == prev) {
if (curr->right)
s.push(curr->right);
} else if (!prev || prev->left == curr || prev->right == curr) {
if (curr->left)
s.push(curr->left);
else if (curr->right)
s.push(curr->right);
} else {
cout << curr->data << " ";
s.pop();
}
prev = curr;
}
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
i**********e
发帖数: 1145 | 9 还有另外一个解是用两个 stack，解法很巧妙，很简洁。这不是我想出来的，在
careercup 上找到的。但是空间复杂度比一个 stack 的解法还要多一些。（O(N)
space，N 是 节点的总数）
解法如下：
1. Push the root node to the first stack.
2. Pop a node from the first stack, and push it to the second stack.
3. Then push its left child followed by its right child to the first
stack.
4. Repeat step 2) and 3) until the first stack is empty.
5. Once done, the second stack would have all the nodes ready to be
traversed in post-order. Pop off the nodes from the second stack one by one
and you're done.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
x***y
发帖数: 633 | 10 This is not post-order..This is the reverse of level by level...
【在 i**********e 的大作中提到】
: 还有另外一个解是用两个 stack，解法很巧妙，很简洁。这不是我想出来的，在
: careercup 上找到的。但是空间复杂度比一个 stack 的解法还要多一些。（O(N)
: space，N 是 节点的总数）
: 解法如下：
: 1. Push the root node to the first stack.
: 2. Pop a node from the first stack, and push it to the second stack.
: 3. Then push its left child followed by its right child to the first
: stack.
: 4. Repeat step 2) and 3) until the first stack is empty.
: 5. Once done, the second stack would have all the nodes ready to be
|
|
|
i**********e
发帖数: 1145 | 11 You are right that it's doing reverse of level by level. But don't judge too
quickly. Once it's done, you popped off the second stack one by one, and
magically, it yields the correct order as in post-order traversal. I dare
you to try it out on a piece of paper first before you hit the reply button
again :)
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 x***y 的大作中提到】
: This is not post-order..This is the reverse of level by level...
|
x***y
发帖数: 633 | 12 Hi, it can not be right...One is related to Breadth and the other is related to
Depth.
simple case
1
/ \
2 3
post-order is 2 3 1; but reverse of level by level is 3 2 1.
too
button
【在 i**********e 的大作中提到】
: You are right that it's doing reverse of level by level. But don't judge too
: quickly. Once it's done, you popped off the second stack one by one, and
: magically, it yields the correct order as in post-order traversal. I dare
: you to try it out on a piece of paper first before you hit the reply button
: again :)
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
i**********e
发帖数: 1145 | 13 Okay, using your example:
First push root (1) to the first stack.
Pop (1) from the first stack, and push it to second stack.
Push left child (2) followed by right child (3) to the first stack.
Pop (3) from the first stack, and push it to second stack.
Since (3) has no left and right child, we skip this step.
Pop (2) from the first stack, and push it to second stack.
Since (2) has no left and right child, we skip this step.
First stack is empty, we stop here.
Now what's the content of the second stack? Pop it off one by one and it
will yield the same as post-order: 2 3 1
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
to
【在 x***y 的大作中提到】
: Hi, it can not be right...One is related to Breadth and the other is related to
: Depth.
: simple case
: 1
: / \
: 2 3
: post-order is 2 3 1; but reverse of level by level is 3 2 1.
:
: too
: button
|
x***y
发帖数: 633 | 14 Hi, it's right. Actually, this approach is not the reverse of level by level
, but it's the reverse of pre-order traversal of the mirror of the original
tree. The first stack is only used for the pre-order of the mirror, and the
second is to reverse. It will be easier to understand if we say it's just a pre-order....
【在 i**********e 的大作中提到】
: Okay, using your example:
: First push root (1) to the first stack.
: Pop (1) from the first stack, and push it to second stack.
: Push left child (2) followed by right child (3) to the first stack.
: Pop (3) from the first stack, and push it to second stack.
: Since (3) has no left and right child, we skip this step.
: Pop (2) from the first stack, and push it to second stack.
: Since (2) has no left and right child, we skip this step.
: First stack is empty, we stop here.
: Now what's the content of the second stack? Pop it off one by one and it
|
A*H
发帖数: 127 | 15 my code
void postOrderIterative(Node *root) {
stack st;
Node *top, *prev;
prev = root;
st.push(root);
while(!st.empty()) {
top = st.top();
if (!top || top->right == prev) {
if (top) cout<data<
prev = top;
st.pop();
}
else {
st.push(top->right);
st.push(top->left);
}
}
} |
