根据中序和后序遍历确定前序
先序和后序可以确定根
再利用根在中序中确定左右子树
#include<bits/stdc++.h>
using namespace std;
int const N=37;
int const M=25e4+7;
int n;
int h[N],z[N];
vector<int>v;
void dfs(int l1,int r1,int l2,int r2){
if(l1>r1||l2>r2) return ;
for(int i=l1;i<=r1;++i){
if(z[i]==h[r2]){
v.push_back(h[r2]);
dfs(l1,i-1,l2,l2-1+i-l1);
dfs(i+1,r1,l2+i-l1,r2-1);
break;
}
}
}
int main(){
cin >> n;
for(int i=1;i<=n;++i) cin >> h[i];
for(int i=1;i<=n;++i) cin >> z[i];
dfs(1,n,1,n);
cout << "Preorder: ";
int len=v.size();
for(int i=0;i<len;++i){
cout << v[i];
if(i!=len-1) cout << " ";
}
return 0;
}
投递华为等公司10个岗位 >
哔哩哔哩三面8人在聊
查看6道真题和解析