L2-006 树的遍历 （25 分）

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

输入格式：

输入第一行给出一个正整数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<string>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)

int post[35],mid[35],level[100005];

void pre(int root,int l,int r,int index)
{
	if(l>r)
		return ;
	int i=l;
	while(i<r&&mid[i]!=post[root])
		i++;
	level[index]=post[root];
	pre(root-1-r+i,l,i-1,index*2+1);
	pre(root-1,i+1,r,index*2+2);
}

int main()
{
	int n,i,cnt=0;
	cin>>n;
	for(i=0;i<n;i++)
		cin>>post[i];
	for(i=0;i<n;i++)
		cin>>mid[i];
	mem(level,-1);
	pre(n-1,0,n-1,0);
	for(i=0;i<=100005;i++)
	{
		if(level[i]!=-1)
		{
			if(cnt!=n-1)
			{
				cout<<level[i]<<" ";
				cnt++;
			}
			else
			{
				cout<<level[i]<<endl;
				break;
			}
		}	
	}
	return 0;
}