翻译和代码思路:Acwing
一个二叉树,树中每个节点的权值互不相同。
现在给出它的后序遍历和中序遍历,请你输出它的层序遍历。
输入格式
第一行包含整数 N,表示二叉树的节点数。
第二行包含 N个整数,表示二叉树的后序遍历。
第三行包含 N 个整数,表示二叉树的中序遍历。
输出格式
输出一行 <span data-mathml="N”>N个整数,表示二叉树的层序遍历。
数据范围
1<=N<=30
输入样例:
72 3 1 5 7 6 41 2 3 4 5 6 7
输出样例:
4 1 6 3 5 7 2
#include#include#include#includeusing namespace std;const int N=40;int a[N],b[N],p[N];int n;vector layer[N]; void Create(int al,int ar,int bl,int br,int d){ if(al>ar) return; int val=a[ar]; int k=p[val]; //当前递归中根节点的位置 int numLeft=k-bl; //左子树的结点树 layer[d].push_back(val); Create(al,al+numLeft-1,bl,bl+numLeft,d+1); Create(al+numLeft,ar-1,k+1,br,d+1);}int main(){ cin>>n; for(int i=0;i>a[i]; for(int i=0;i>b[i]; for(int i=0;i<n;i++) p[b[i]]=i; //记录中序遍历结点的位置 Create(0,n-1,0,n-1,0); //创建树 for(int i=0;i<n;i++){ for(auto x:layer[i]){ cout<<x<<" "; } } return 0;}