翻譯和代碼思路：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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/548968.html
標籤：其他
下一篇：Thanos作業原理及組件簡介