PAT 甲级 1127 ZigZagging on a Tree (30 分)

思路：

1.根据两个序列构造一棵树；
2.奇数层次从左往右遍历孩子，偶数层次从右往左遍历孩子；
3.每层在遍历时，按自己的遍历顺序，将每个遍历到的孩子结点入栈，此栈将作为下一层的遍历序列；
（用栈的理由：自己在草稿纸上模拟一遍就出来了，是FIFO模型）

代码：

#include<iostream>
#include<unordered_map>
#include<vector>
#include<stack>
using namespace std;
unordered_map<int,vector<int>> mp;
unordered_map<int,int> lca;
vector<int> in,post;
void buildTree(int inb,int ine,int pb,int pe){
	int root=lca[post[pe]];
	if(root>inb&&root<=ine){
		mp[post[pe]].push_back(post[root-1-inb+pb]);
		buildTree(inb,root-1,pb,root-1-inb+pb);
	}
	if(root<ine&&root>=inb){
		mp[post[pe]].push_back(post[pe-1]);
		buildTree(root+1,ine,root-inb+pb,pe-1);
	}
}
int main(){
	int n;
	scanf("%d",&n);
	in.resize(n);
	post.resize(n);
	for(int i=0;i<n;i++){
		scanf("%d",&in[i]);
		lca[in[i]]=i;
	}
	for(int i=0;i<n;i++) scanf("%d",&post[i]);
	buildTree(0,n-1,0,n-1);
	stack<int> s1;
	s1.push(post[n-1]);
	printf("%d",post[n-1]);
	for(int i=1;!s1.empty();i++){
		stack<int> s2;
		for(;!s1.empty();s1.pop()){
			int nd=s1.top();
			for(int j=0;j<mp[nd].size();j++){
				int index=i%2==1?j:mp[nd].size()-1-j;
				s2.push(mp[nd][index]);
				printf(" %d",mp[nd][index]);
			}
		}
		s1=s2;
	}
	return 0;
}