03-树2. Tree Traversals Again (25)

根据姥姥提示，入栈顺序就是先序遍历，出栈顺序就是中序遍历。然后在用solve函数进行递归分治来求出后序遍历的结果。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include<stack>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
int pre[50],in[50],post[50];

void solve(int prel,int inl,int postl,int m)
{
    int i;
    if(m==0) return;
    else if(m==1) {post[postl]=pre[prel];return;}
    else post[postl+m-1]=pre[prel];
    for(i=0;i<m;i++)
    {
        if(in[i+inl]==pre[prel]) break;
    }
    solve(prel+1,inl,postl,i);
    solve(prel+i+1,inl+i+1,postl+i,m-i-1);
}

int main()
{
    int i,t,j,k,n;
    char c[10];
    stack<int>q;
    while(~scanf("%d",&n))
    {
        while(!q.empty()) q.pop();
        j=k=0;
        for(i=1; i<=2*n; i++)
        {
            scanf("%s",c);
            if(strcmp(c,"Push")==0)
            {
                scanf("%d",&t);
                q.push(t);
                pre[j++]=t;
            }
            else
            {
                t=q.top();
                in[k++]=t;
                q.pop();
            }
        }
        solve(0,0,0,n);
        for(i=0; i<n; i++)
        {
            if(!i)printf("%d",post[i]);
            else printf(" %d",post[i]);
        }

        printf("
");
    }
    return 0;
}