由先序遍历和中序遍历得到后序遍历和层次遍历（二叉树）

前几天写了这个题目，明白了如何由二叉树的后序遍历和中序遍历得到先序遍历和层次遍历。受这道题启发，思考了一下如何由二叉树的先序遍历和中序遍历得到后序遍历和层次遍历。思路和由二叉树的后序遍历和中序遍历得到先序遍历和层次遍历一样，只是递归函数的参数和位置有些改动。

最后附上我的代码

由先序遍历和中序遍历得到后序遍历

#include <iostream>
#include <map>
#include <vector>
using namespace std;
vector <int> pre,in;
void post(int root,int start,int end)
{
	if(start>end)
		return;	
	int i=start;
	while(i<end&&pre[root]!=in[i])
		i++;
	post(root+1,start,i-1);
	post(i+1+root-start,i+1,end);	
	cout<<pre[root]<<" "; 
} 
int main()
{
	int n,temp;
	cin>>n;
	for(int i=0;i<n*2;i++)
	{
		cin>>temp;
		if(i<n)
			pre.push_back(temp);
		else
			in.push_back(temp);
	}
	post(0,0,n-1);
	return 0;
}

由先序遍历和中序遍历得到层次遍历

#include <iostream>
#include <map>
#include <vector>
using namespace std;
vector <int> pre,in;
map<int,int> level;
void post(int root,int start,int end,int index)
{
	if(start>end)
		return;	
	int i=start;
	while(i<end&&pre[root]!=in[i])
		i++;
	post(root+1,start,i-1,index*2+1);
	post(i+1+root-start,i+1,end,index*2+2);	
	level[index]=pre[root];
} 
int main()
{
	int n,temp;
	cin>>n;
	for(int i=0;i<n*2;i++)
	{
		cin>>temp;
		if(i<n)
			pre.push_back(temp);
		else
			in.push_back(temp);
	}
	post(0,0,n-1,0);
	map<int,int>::iterator it;
	for(it=level.begin();it!=level.end();it++)
	{
        if(it!=level.begin())
			cout<<" ";
		cout<<it->second;
	} 
	return 0;
}