1086 Tree Traversals Again （25 分）（二叉樹的遍歷）

用棧來模擬一棵二叉樹的先序遍歷和中序遍歷過程，求這棵二叉樹的後序遍歷

由題棵知道：push是先序遍歷

                      pop是中序遍歷

#include<bits/stdc++.h>

using namespace std;
vector<int>pre;
vector<int>in;
vector<int>vec;
const int N=50;
int pre1[N];
int in1[N];
void print(int l1,int r1,int l2,int r2)
{
    if(l1>r1||l2>r2) return;
    int mid=l2;
    while(in[mid]!=pre[l1]) mid++;
    print(l1+1,l1+mid-l2,l2,mid-1);
    print(l1+mid-l2+1,r1,mid+1,r2);
    vec.push_back(pre[l1]);
}
int main()
{
    int n;
    scanf("%d",&n);
    stack<int>st;
    for(int i=0;i<2*n;i++){
        char s[20];
        scanf("%s",s);
        if(strcmp(s,"Push")==0){
            int num;
            scanf("%d",&num);
            st.push(num);
            pre.push_back(num);
        }
        else{
            int t=st.top();
            st.pop();
            in.push_back(t);
        }
    }

    print(0,n-1,0,n-1);
    for(int i=0;i<vec.size();i++){
        if(i) printf(" ");
        printf("%d",vec[i]);
    }
    printf("\n");
    return 0;
}