<pre><small><small>
An inorder binary tree traversal
can be implemented in a non-recursive way with a stack.
For example, suppose that
when a 6-node binary tree (with the keys numbered from 1 to 6)
is traversed,
the stack operations are:
push(1); push(2); push(3); pop(); pop();
push(4); pop(); pop(); push(5); push(6);
pop(); pop().
Then a unique binary tree (shown in Figure 1)
can be generated from this sequence of operations.
Your task is to give the postorder traversal sequence of this tree.
</small></small></pre>

图片1
<pre><small><small>
Input Specification:
Each input file contains one test case.
For each case,
the first line contains a positive integer N (<=30)
which is the total number of nodes in a tree
(and hence the nodes are numbered from 1 to N).
Then 2N lines follow,
each describes a stack operation in the format:
"Push X" where X is the index of the node
being pushed onto the stack;
or "Pop" meaning to pop one node from the stack.
</small></small></pre>
<pre><small><small>
Output Specification:
For each test case,
print the postorder traversal sequence
of the corresponding tree in one line.
A solution is guaranteed to exist.
All the numbers must be separated by exactly one space,
and there must be no extra space at the end of the line.
</small></small></pre>
<pre><small><small>
Sample Input:
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop
</small></small></pre>
<pre><small><small>
Sample Output:
3 4 2 6 5 1
</small></small></pre>
<pre><small><small>

include <stdio.h>

include <stdlib.h>

include <string.h>

typedef struct
{
int * a;
int top;
}SeqStack;

void push(SeqStack * pS, int X);
int pop(SeqStack * pS);
void solve(int * pre, int * in, int * post,int preL, int inL, int postL, int n);
</small></small></pre>
<pre><small><small>
int main()
{
// freopen("in.txt", "r", stdin); // for test
int i, N;
scanf("%d", &N);

SeqStack S;
S.a = (int \*)malloc(N \* sizeof(int));
S.top = -1;
int pre[N], in[N], post[N];

char chars[5];
char \* str = chars;
int X, pre_index, in_index;
pre_index = in_index = 0;
for(i = 0; i < 2 \* N; i++)
{
    scanf("%s", str);
    if(strcmp(str, "Push") == 0)
    {
        scanf("%d", &X);
        pre[pre_index++] = X;
        push(&S, X);
    }
    else
        in[in_index++] = pop(&S);
}

solve(pre, in, post, 0, 0, 0, N);
for(i = 0; i < N; i++)
{
    printf("%d", post[i]);
    if(i < N - 1)
        printf(" ");
    else
        printf("\n");
}

// fclose(stdin); // for test
return 0;
}
</small></small></pre>
<pre><small><small>
void push(SeqStack * pS, int X)
{
pS->a[++(pS->top)] = X;
}

int pop(SeqStack * pS)
{
return pS->a[pS->top--];
}
</small></small></pre>
<pre><small><small>
void solve(int * pre, int * in, int * post, int preL, int inL, int postL, int n)
{
int i, root, L, R;

if(n == 0)
    return;
if(n == 1)
{
    post[postL] = pre[preL];
    return;
}
root = pre[preL];
post[postL + n - 1] = root;
for(i = 0; i < n; i++)
    if(in[inL + i] == root)
        break;
L = i;
R = n - L - 1;
solve(pre, in, post, preL + 1, inL, postL, L);
solve(pre, in, post, preL + L + 1, inL + L + 1, postL + L, R);

}
</small></small></pre>