看到节点这么多，以为递归进去会超时，但是并没有，四次方递归不会超时，心里记一下
模板题目，后序和中序重建二叉树，之后后序遍历
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 5e4 + 10;
int pre[maxn], in[maxn];
struct node {
int data;
node *lchild, *rchild;
};
vector<int>ans;
node* create(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] == root->data)break;
}
int numleft = k - inL;
root->lchild = create(preL + 1, preL + numleft, inL, k - 1);
root->rchild = create(preL + numleft + 1, preR, k + 1, inR);
return root;
}
void postorder(node* root)
{
if (root == NULL)return;
postorder(root->lchild);
postorder(root->rchild);
ans.push_back(root->data);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)scanf("%d", &pre[i]);
for (int i = 0; i < n; i++)scanf("%d", &in[i]);
node*root = create(0, n - 1, 0, n - 1);
postorder(root);
printf("%d", ans[0]);
return 0;
}
