7-10 树的遍历 （25 分）_7-1 二叉树的遍历!(简单) (10 分)

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cctype>
using namespace std;
int n,i;
int h[35],z[35],Tree[100010],mx=0;
typedef struct tree{
	int data;
	tree *l,*r;
}tree;
int search(int l1,int r1,int l2,int r2)
{
	for(int i=l2;i<=r2;i++)
	{
		if(z[i]==h[r1])
		return i;
	}
}
tree* creat(int l1,int r1,int l2,int r2,int n,int w)
{
	tree* t;
	t=(tree*)malloc(sizeof(tree));
	t->data=h[r1];
	Tree[w]=h[r1];
	mx=max(mx,w);
	if(n==0)
	{
		t->l=NULL;
		t->r=NULL;
	}
	else
	{
		int f;
		f=search(l1,r1,l2,r2);
		int n1=f-l2,n2=r2-f;
		if(f!=l2)
		t->l=creat(l1,l1+n1-1,l2,f-1,f-l2,w*2);
		else
		t->l=NULL;
		if(f!=r2)
		t->r=creat(l1+n1,r1-1,f+1,r2,r2-f,w*2+1);
		else
		t->r=NULL;
	}
	return t;
}
void remove_tree(tree* root)
{
	if(root!=NULL)
	{
		remove_tree(root->l);
		remove_tree(root->r);
		free(root);
	}
}
int main()
{
	cin>>n;
	memset(Tree,0,sizeof(Tree));
	for(i=1;i<=n;i++)
	cin>>h[i];
	for(i=1;i<=n;i++)
	cin>>z[i];
	tree* root;
	root=creat(1,n,1,n,n,1);
	for(i=1;i<=mx;i++)
		if(Tree[i]!=0)
		{
			printf("%d",Tree[i]);
			if(i<mx)
			printf(" ");
		}
	remove_tree(root);
	return 0;
}