d****n
发帖数: 233 | 1 Do postorder traversal without using recursion.
You can't modify the tree node struct which is as following:
struct Node {
int data;
Node *left;
Node *right;
}
If you want to use stack, use no more than 1 stack.
Any idea?: |
B*****t
发帖数: 335 | 2 贴个代码仅供参考
void postOrder() {
Node *p = root, *visited = 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 == visited) {
visit(p->c);
st.pop();
visited = p;
p = NULL;
}
else
p = p->right;
}
}
【在 d****n 的大作中提到】
: Do postorder traversal without using recursion.
: You can't modify the tree node struct which is as following:
: struct Node {
: int data;
: Node *left;
: Node *right;
: }
: If you want to use stack, use no more than 1 stack.
: Any idea?:
|
d****n
发帖数: 233 | 3 Nice, saved to my library. Thanks.
【在 B*****t 的大作中提到】
: 贴个代码仅供参考
: void postOrder() {
: Node *p = root, *visited = root;
: stack st;
: int i = 0;
: while(!st.empty() || p){
: while(p){
: st.push(p);
: p = p->left;
: }
|
m*****g
发帖数: 226 | 4 不是很明白。高手评价一下：
void postOrderTraversal(node *root)
{
stack st;
st.push(root);
st.push(root);
node *curNode;
node *visited;
while(!st.empty())
{
visited=st.top();
st.pop();
curNode=st.top();
st.pop();
if(!(curNode->left&&curNode->right)) {printf(curNode); st.push(curNode)
; continue;}
if(curNode->left && (curNode->left != visited))
{ st.push(curNode);
if(curNode->right) st.push(curNode->right);
st.push(curNode->left);
【在 d****n 的大作中提到】
: Do postorder traversal without using recursion.
: You can't modify the tree node struct which is as following:
: struct Node {
: int data;
: Node *left;
: Node *right;
: }
: If you want to use stack, use no more than 1 stack.
: Any idea?:
|
z*j
发帖数: 42 | 5 说说我的理解:
基本上是在用栈模拟递归的后序遍历过程
对栈顶node, 要判断这个node是回溯过来的,还是刚push到栈顶的
case1:栈顶node左右孩子皆空, 到了叶节点.接下来就要回溯啦.
case2:左孩子回溯回来, 则访问右孩子(2sub cases)
case3:右孩子回溯回来, 则访问栈顶节点, 同时栈顶节点出栈
剩下case 是栈顶不是回溯回来的, 则继续压栈(深度优先搜索) |
c*********n
发帖数: 1057 | 6 我想问下这是面试完以后给布置的么？
【在 d****n 的大作中提到】
: Do postorder traversal without using recursion.
: You can't modify the tree node struct which is as following:
: struct Node {
: int data;
: Node *left;
: Node *right;
: }
: If you want to use stack, use no more than 1 stack.
: Any idea?:
|
l********s
发帖数: 30 | 7 我的想法和你类似，但不尽一样：
1. if root is empty, return
2. stack.push(root)
3. let prev_print point to the previous node printed. initially, it points
to a dummy node.
3. while stack is not empty
4. case 1: stack.top is a leaf node. print it.
let prev_print point to stack.top. pop stack.
5. case 2: prev_print is a child of stack.top.
let prev_print point to stack.top. pop stack.
6. case 3: otherwise.
push stack.top's children to stack in right first o
【在 z*j 的大作中提到】
: 说说我的理解:
: 基本上是在用栈模拟递归的后序遍历过程
: 对栈顶node, 要判断这个node是回溯过来的,还是刚push到栈顶的
: case1:栈顶node左右孩子皆空, 到了叶节点.接下来就要回溯啦.
: case2:左孩子回溯回来, 则访问右孩子(2sub cases)
: case3:右孩子回溯回来, 则访问栈顶节点, 同时栈顶节点出栈
: 剩下case 是栈顶不是回溯回来的, 则继续压栈(深度优先搜索)
|
l****q
发帖数: 177 | 8 有简单的做法：
p = q = root;
while(p!=0)
{
for( ; p->left! = 0 ; p = p->left)
stack.push(p);
while(p != 0 && ( p->right == 0 || p->right == q))
{
//print p
q = p;
if(stack.empty())
return;
p = stack.pop();
}
stack.push(p);
p = p->right;
}
简化在于两点：叶子不要push in； pop out之后的可以再push in |
