PAT L2-006【二叉树中序后序构造树】

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

struct BT{

	int w;

	BT *L;

	BT *R;

};

BT* Creat(int *post,int *in,int n)

{

	BT* p;

	for(int i=0;i<n;i++)

	{

		if(post[n-1]==in[i])

		{

			p=(BT*)malloc(sizeof(BT));

			p->w=in[i];

			p->L=Creat(post,in,i);

			p->R=Creat(post+i,in+i+1,n-(i+1));

			return p;

		}

	}

	return NULL;

}

int main()

{

	int post[35],in[35],n;

	BT* root;

	scanf("%d",&n);

	for(int i=0;i<n;i++)

		scanf("%d",&post[i]);

	for(int i=0;i<n;i++)

		scanf("%d",&in[i]);

	root=Creat(post,in,n);

	queue<BT*>q;

	q.push(root);

	bool flag=false;

	while(!q.empty())

	{

		BT* now=q.front();q.pop();

		if(flag) printf(" ");

		printf("%d",now->w);

		if(now->L) q.push(now->L);

		if(now->R) q.push(now->R);

		flag=true;

	}

	return 0;

}

巴特西

PAT L2-006【二叉树中序后序构造树】

最新文章

热门文章