PAT甲级1086.

目录

A1086

题目

样例

输入:

6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

输出:

3 4 2 6 5 1

思路和坑点

　　通树的先序和中序的非递归算法可以直到，栈的push序列是其先序序列，pop序列是其中序序列。因此通过栈的模拟分别获得先序和中序序列，然后由此建树，可以直接在递归函数中加一个后序的下标位置作为参数，直接获得后序遍历的结果。

AC代码

#include<bits/stdc++.h>
using namespace std;
vector<int> pre,in,post;                //用于存放先序、中序、后序的序列 

//树的后序序列创建函数
//pl，pr，il，ir，pos分别表示当前的先序序列的左右端下标，中序序列的左右下标，以及在后序中根的位置 
void creat(int pl,int pr,int il,int ir,int pos){ 
    if(pl>pr) return;                   //如果当前递归的子树中没有结点，直接返回 
    post[pos]=pre[pl];                  //先序的第一个便是根，放在后序序列的相应位置上 
    int k,leftnum,rightnum;             //k表示根在中序中的位置下标，leftnum和rightnum分别表示左右子树元素个数 
    for(k=il;k<=ir;k++){                //确定k 
        if(in[k]==pre[pl])
            break;
    }
    leftnum=k-il;    rightnum=ir-k;    //确定左右子树的元素个数 
    creat(pl+1,pl+leftnum,il,k-1,pos-rightnum-1);       //递归左子树 
    creat(pl+leftnum+1,pr,k+1,ir,pos-1);                //递归右子树 
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n;
    scanf("%d",&n);
    post.resize(n);
    stack<int> s;
    for(int i=0;i<n*2;i++){                             //有n*2此操作 
        string tag;                                    
        cin>>tag;                                       //操作的类型 
        if(tag=="Push"){
            int num;    scanf("%d",&num);               //如果是push，读入相应的数字分别压入栈和前序序列中 
            pre.push_back(num);
            s.push(num);
        }
        else{
            in.push_back(s.top());                      //如果是pop，出栈顺序为中序序列，并从栈中出栈 
            s.pop();
        }
    } 
    creat(0,n-1,0,n-1,n-1);                            //建树并输出 
    for(int i=0;i<n;i++){
        if(i) putchar(' ');
        printf("%d",post[i]);
    }
    return 0;
}