1138. Postorder Traversal (25)

#include <iostream>
#include <vector>
#include <algorithm>
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;
  postorder(root->l);
  postorder(root->r);
  post.push_back(root->data);
}


int main()
{
  cin >> n;
  pre.resize(n);
  in.resize(n);
  for(int i = 0; i < n; i++) cin >> pre[i];
  for(int i = 0; i < n; i++) cin >> in[i];
  node *root = build(0, n-1, 0, n-1);
  postorder(root);
  cout << post[0] << endl;
  return 0;
}