题目：1497. 树的遍历
题目描述
一个二叉树，树中每个节点的权值互不相同。
现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。
输入
第一行包含整数 N，表示二叉树的节点数。
第二行包含 N 个整数，表示二叉树的后序遍历。
第三行包含 N 个整数，表示二叉树的中序遍历。
输出
输出一行 N 个整数，表示二叉树的层序遍历。
数据范围
1≤N≤30,
官方并未给出各节点权值的取值范围，为方便起见，在本网站范围取为 1∼N。
时空限制
1s / 64MB
输入样例
7 2 3 1 5 7 6 4 1 2 3 4 5 6 7输出样例
4 1 6 3 5 7 2代码
#include<bits/stdc++.h>usingnamespacestd;constintN=30+10;intn,postorder[N],inorder[N];unordered_map<int,int>pos,l,r;boolvis[N];//pos是中序遍历序列中每个元素的下标//l是左子树//r是右子树intbuild(intpl,intpr,intil,intir){introot=postorder[pr];intm=pos[root];if(il<m)l[root]=build(pl,pl+m-1-il,il,m-1);if(m<ir)r[root]=build(pl+m-il,pr-1,m+1,ir);returnroot;}voidbfs(intsx){queue<int>q;q.push(sx);vis[sx]=true;cout<<sx<<" ";while(!q.empty()){intt=q.front();q.pop();if(l.count(t)&&!vis[l[t]]){q.push(l[t]);vis[l[t]]=true;cout<<l[t]<<" ";}if(r.count(t)&&!vis[r[t]]){q.push(r[t]);vis[r[t]]=true;cout<<r[t]<<" ";}}}intmain(){cin>>n;for(inti=0;i<n;i++)cin>>postorder[i];for(inti=0;i<n;i++){cin>>inorder[i];pos[inorder[i]]=i;}introot=build(0,n-1,0,n-1);bfs(root);return0;}
