PAT A1086 Tree Traversals Again (25分)

要認清該題的本質是已知先序序列和中序序列，求后序序列

#include<cstdio>
#include<stack>
#include<vector>
#include<string.h>
using namespace std;
const int N = 31;
struct node{
    int v;
    int left=-1;
    int right=-1;
}Node[N];//Node[add].v = add;一一映射
vector<int> preOrder,inOrder,postOrder;
//[pL,pR],[inL,inR]
int maketree(int pL,int pR ,int inL,int inR){
    if(pL <= pR){
        int root = preOrder[pL];
        Node[root].v = preOrder[pL];
        for(int i = inL;i <= inR;i++){
            if(Node[root].v==inOrder[i]){
                int c = i - inL;
                Node[root].left=maketree(pL+1,pL+c,inL,i-1);
                Node[root].right=maketree(pL+c+1,pR,i+1,inR);
            } 
        }
        return root;
    }
    return -1;
}

void postOrderf(int root){
    if(root == -1) return ;
    postOrderf(Node[root].left);
    postOrderf(Node[root].right);
    postOrder.push_back(Node[root].v);
}

int main(){
    int n;
    scanf("%d",&n);
    int root;
    char type[5];
    stack<int> st;
    for(int i = 0;i < 2*n;i++){//讀入n個數字
        int id;
        scanf("%s",type);
        if(strcmp(type,"Push")==0){
            scanf("%d",&id);
            preOrder.push_back(id);
            st.push(id);
        }else{
            if(st.empty()==false){//非空
                int top = st.top();
                st.pop();
                inOrder.push_back(top);
            }
        }
    }
    //得到先序遍歷和中序遍歷，建立樹
    int len = preOrder.size();
    root = maketree(0,len-1,0,len-1);
    postOrderf(root);
    for(int i = 0;i<len;i++){
        printf("%d",postOrder[i]);
        if(i!=len-1) printf(" ");
    }
    return 0;
}