题目链接：点击打开链接
题目大意：给出中序和后序序列，按照“S”形层序遍历输出。
解题思路：找规律可以发现，只要每次用queue保存，然后遍历了该层的所有结点后，把queue里的结点弹到stack里即可。注意的是，这里需要每次从哪个头开始弹入queue里，需要想好是先 l,r or r,l。
AC 代码
usingnamespacestd; typedeflonglongll; structnode{ intd,l,r; }T[40]; intn; intin[40], post[40], lvl[40]; intcreate(intl1,intr1, intl2,intr2, intl) // in post{ if(l1>r1) return-1; lvl[l]++; intrt=r2; intp1=l1,p2; while(in[p1]!=post[r2]) p1++; p2=p1-l1; T[rt].d=post[rt]; T[rt].l=create(l1,p1-1,l2,l2+p2-1,l+1); T[rt].r=create(p1+1,r1,l2+p2,r2-1,l+1); returnrt; } voidbfs(intrt) { queue<int>q; vector<int>v; stack<int>sk; q.push(rt); nodend; intth=0, cnt=0; while(v.size()<n) { if(!sk.empty()) rt=sk.top(), sk.pop(); elseif(!q.empty()) rt=q.front(), q.pop(); v.push_back(T[rt].d), cnt++; if(th%2==0) { if(T[rt].r!=-1) q.push(T[rt].r); if(T[rt].l!=-1) q.push(T[rt].l); } else { if(T[rt].l!=-1) q.push(T[rt].l); if(T[rt].r!=-1) q.push(T[rt].r); } if(lvl[th]==cnt) { cnt=0, th++; while(!q.empty()) sk.push(q.front()), q.pop(); } } for(inti=0;i<v.size();i++) printf("%d%c",v[i],i==v.size()-1?'\n':' '); } intmain() { intrt; scanf("%d",&n); for(inti=0;i<n;i++) scanf("%d",&in[i]); for(inti=0;i<n;i++) scanf("%d",&post[i]); rt=create(0,n-1,0,n-1,0); bfs(rt); return0; }
