#include <bits/stdc++.h>
#define DataType Tree*
using namespace std;

typedef struct Tree{
    int data;
    struct Tree *lchild,*rchild;
};

typedef struct Stack{
    DataType data[100];
    int top;
}Stack;

void push_stack(Stack *s,DataType data){
    s -> data[s -> top++] = data;
}

DataType pop_stack(Stack *s){
    return s -> data[--s -> top];
}

DataType get_top(Stack *s){
    return s -> data[s -> top - 1];
}

bool isEmpty(Stack *s){
    return s -> top == 0;
}

unordered_map<int,int> ur_map;

void init_map(int inOrder[],int size){
    for (int i = 0; i < size; ++i) {
        ur_map[inOrder[i]] = i;
    }
}

Tree* init_tree(int postOrder[],int postStart,int postEnd,
                int inOrder[],int inStart,int inEnd){
    if(postStart > postEnd || inStart > inEnd){
        return NULL;
    }
    else{
        Tree *t = new Tree;
        t -> data = postOrder[postEnd];
        int rootIdx = ur_map[postOrder[postEnd]];
        int len = rootIdx - inStart;
        t -> lchild = init_tree(postOrder,postStart,postStart + len - 1,
                                inOrder,inStart,rootIdx - 1);
        t -> rchild = init_tree(postOrder,postStart + len,postEnd - 1,
                                inOrder,rootIdx + 1,inEnd);
        return t;
    }
}

void preTravel(Tree *t){
    Stack *s = new Stack;
    s -> top = 0;
    push_stack(s,t);
    while(!isEmpty(s)){
        Tree *cur = pop_stack(s);
        cout << cur -> data << " ";
        if(cur -> rchild != NULL){
            push_stack(s,cur -> rchild);
        }
        if(cur -> lchild != NULL){
            push_stack(s,cur -> lchild);
        }
    }
}

int main(){
    int inOrder[] = {1,2,4,5,3,6,7};
    int postOrder[] = {4,5,2,6,7,3,1};
    init_map(postOrder,7);
    Tree *t = init_tree(postOrder,0,6,
                        inOrder,0,6);
    preTravel(t);
}