翻译和代码思路: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;}