题目链接：点击打开链接
题目大意：前序 + 中序 => 后序第一位元素。
解题思路：之前都是用给出的序列值作为下标，发现这题用这种办法会段错误，因为题目没说给出的序列值是在下标1~N范围内，所以要用纯粹的下标来做。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define ssclr(ss) ss.clear(), ss.str("") #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; const int maxn=5e4+1000; int f; int pre[maxn], in[maxn]; struct node { int l,r,d; }T[maxn]; int create(int l1,int r1,int l2,int r2) // in pre { if(l2>r2) return -1; int rt=l2; int p1=l1,p2; while(in[p1]!=pre[rt]) p1++; p2=p1-l1; T[rt].d=pre[rt]; T[rt].l=create(l1,p1-1,l2+1,l2+p2); T[rt].r=create(p1+1,r1,l2+p2+1,r2); return rt; } void postT(int rt) { if(rt==-1 || !f) return; postT(T[rt].l); postT(T[rt].r); if(f) f=0, printf("%d\n",T[rt].d); } 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]); int rt=create(0,n-1,0,n-1); f=1, postT(rt); return 0; }
