#include<iostream>
#include<cstring>
#include<unordered_map>
using namespace std;
const int N=50010;
int n;
unordered_map<int,int> pos;
int preorder[N],inorder[N];
bool is_first=true;
void build(int il,int ir,int pl,int pr)
{
int root=preorder[pl];
int k=pos[root];
if(il<k) build(il,k-1,pl+1,pl+1+(k-1-il));
if(k<ir) build(k+1,ir,pl+1+(k-1-il)+1,pr);
if(is_first)
{
cout<<root;
is_first=false;
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>preorder[i];
for(int i=0;i<n;i++)
{
cin>>inorder[i];
pos[inorder[i]]=i;
}
build(0,n-1,0,n-1);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=50010;
int n;
int pre[N],in[N];
unordered_map<int,int> pos;
int post[N],post_i;
void build(int il,int ir,int pl,int pr)
{
int root=pre[pl];
int k=pos[root];
if(il<k) build(il,k-1,pl+1,pr+1+(k-1-il));
if(k<ir) build(k+1,ir,pl+1+(k-1-il)+1,pr);
post[post_i++]=root;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> pre[i];
for (int i = 0; i < n; i ++ )
{
cin >> in[i];
pos[in[i]] = i;
}
build(0,n-1,0,n-1);
cout<<post[0]<<endl;
return 0;
}
要是有中后遍历求先序遍历,该怎样改啊?
赋值放到两次递归之前就行了