做了vijos 1132以后做这题轻松多了,略微调试了下就ac了,关键就是通过递归去找节点
前+中->后
#include<iostream>
#include<malloc.h>
#define maxn 1000+5
using namespace std;
int n;
int qi[maxn],zh[maxn];
int t=0;
struct root
{
int num;
root *left,*right;
};
void build(root* &s,int as,int ae,int bs,int be)
{
s=(root*)malloc(sizeof(root));
s->num=qi[as];
s->left=s->right=NULL;
int x=bs;
while(zh[x]!=qi[as]) x++;
int l=x-bs;
if(x>bs) build(s->left,as+1,as+l,bs,x⑴);
if(x<be) build(s->right,as+l+1,ae,x+1,be);
}
void pi(root *s)
{
if(s!=NULL)
{
pi(s->left);
pi(s->right);
if(!t) cout<<s->num;
else cout<<" "<<s->num;
t++;
}
}
int main()
{
while(cin>>n)
{
t=0;
for(int i=1;i<=n;i++) cin>>qi[i];
for(int i=1;i<=n;i++) cin>>zh[i];
root *head;
build(head,1,n,1,n);
pi(head);
cout<<endl;
}
return 0;
}