树

建树

题目详情 (pintia.cn)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<set>
#include<vector>
#define rep(i,x,y) if ((x)<=(y)) for (register int i=(x);i<=(y);i++)
using namespace std;
struct node{
	int data;
	node *l;
	node *r;
	int level;
};
int in[100],pre[100];
bool vis[100];
vector <int> ans;
node* createtree(int prel,int pren,int inl,int inn)
{
	int k,ini=0;
	if (prel>pren)
	  return NULL;
	node* root =(node*)malloc(sizeof(struct node));
	for (ini=inl;ini<=inn;ini++)
		if (in[ini]==pre[prel])
		  break;
	k=ini-inl;
	root->data=in[ini];
	root->l=createtree(prel+1,prel+k,inl,ini-1);
	root->r=createtree(prel+k+1,pren,ini+1,inn);
	return root;
}

void cal(node* root)
{
	if (root->l!=NULL)
	{
		root->l->level=root->level+1;
		if (!vis[root->l->level])
			ans.push_back(root->l->data);
		vis[root->l->level]=true;
		cal(root->l);
	}
	if (root->r!=NULL)
	{
		root->r->level=root->level+1;
		if (!vis[root->r->level])
			ans.push_back(root->r->data);
		vis[root->r->level]=true;
		cal(root->r);
	}
}
	
int main()
{
	int n;
	cin>>n;
	rep(i,1,n)
	  scanf("%d",&in[i]);
	rep(i,1,n)
	  scanf("%d",&pre[i]);
	node* root = createtree(1,n,1,n);
	ans.push_back(root->data);
	cal(root);
	cout<<ans[0];
	rep(i,1,ans.size()-1)
	  cout<<' '<<ans[i];
	return 0;
}