1252: Tree Recovery

http://tjuacm.chaosheng.top/problem.php?id=1252

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>

using namespace std;

string preorder, inorder, postorder;
map<char, int> pos;

struct TreeNode{
    char val;
    TreeNode* l;
    TreeNode* r;
};

TreeNode* makeTree(int il, int ir, int pl, int pr){
    if(pl > pr) return NULL;
    int k = pos[preorder[pl]];
    TreeNode* root = new TreeNode();
    root->val = inorder[k];
    root->l = makeTree(il, k-1, pl + 1, pr + k - ir);
    root->r = makeTree(k + 1, ir, pr + k - ir + 1, pr);
    return root;
}

void post_order(TreeNode* root){
    if(root == NULL){
        return ;
    }
    post_order(root->l);
    post_order(root->r);
    postorder += root->val;
}
int main(){
    while(cin >> preorder){
        cin >> inorder;
        int n = preorder.size();
        for(int i = 0; i < n; i++){
            pos[inorder[i]] = i;
        }
        TreeNode* root = makeTree(0, n-1, 0, n-1);
        postorder = "";
        post_order(root);
        cout << postorder << endl;
    }
    return 0;
}