PAT甲级真题1020.树的遍历

翻译和代码思路：Acwing

一个二叉树，树中每个节点的权值互不相同。

现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。

输入格式

第一行包含整数 N，表示二叉树的节点数。

第二行包含 N个整数，表示二叉树的后序遍历。

第三行包含 N 个整数，表示二叉树的中序遍历。

输出格式

输出一行 N个整数，表示二叉树的层序遍历。

数据范围

1<=N<=30

输入样例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=40;
int a[N],b[N],p[N];
int n;
vector<int> 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<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>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;
}