1086. Tree Traversals Again (25)

//push是前序遍历 pop是中序遍历 根据前序遍历和中序遍历 输出后序遍历
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int n;
vector<int> pre, in, post;
struct node { int data; node *l, *r; };
node *build(int preL, int preR, int inL, int inR){
    if(preL > preR) return NULL;
    node *root = new node;
    root->data = pre[preL];
    int k;
    for (k = inL; k <= inR; k++)
        if(in[k] == pre[preL]) break;
    int leftnum = k - inL;
    root->l = build(preL + 1, preL + leftnum, inL, k - 1);
    root->r = build(preL + leftnum + 1, preR, k + 1, inR);
    return root;
}
void postOrder(node *root){
    if (root == NULL) return;
    if(root->l) postOrder(root->l);
    if(root->r) postOrder(root->r);
    post.push_back(root->data);
}

int main(){
    cin >> n;
    stack<int> st;
    for (int i = 0; i < n * 2; i++) {
        string s;
        cin >> s;
        if (s == "Push") {
            int t;
            cin >> t;
            st.push(t);
            pre.push_back(t);
        }else{
            int t = st.top();
            st.pop();
            in.push_back(t);
        }
    }
    node *root = build(0, n - 1, 0, n - 1);
    postOrder(root);
    for (int i = 0; i < n; i++)
        printf("%d%c", post[i], i == n - 1 ? '\n' : ' ');

    return 0;
}