已知后序中序，求先序

利用后序遍历的最后一个元素（根结点），在中序遍历中找到它，分割为左子树和右子树，然后在后序遍历中找到子树的根结点、起点、终点，分别递归。

#include<iostream>
using namespace std;

#define n 6
int post[n]={3,4,2,6,5,1};
int in[n]={3,2,4,1,6,5};

void pre(int rootPo,int start,int end); 

int main()
{
	int rootPo=n-1,start=0,end=n-1;
	pre(rootPo,start,end);  //后序遍历根结点位置，中序遍历开始和结束位置 
	
	return 0;
} 

void pre(int rootPo,int start,int end)
{
	if(start>end) return;
	
	int rootIn=start;  //开始查找根结点在In[]中的位置 
	while((rootIn<end)&&(in[rootIn]!=post[rootPo]))
	{	
		rootIn++;  //得到根结点在in[]中的位置 
	}
	//cout<<rootIn<<endl;
	cout<<in[rootIn]<<endl;
	
	int leftrootPo=rootPo-(end-rootIn)-1;  //左子树的根结点在后序遍历中的位置。(end-rootIn)：右子树的结点个数 
	int leftstart=start;  //左子树在中序遍历的开始位置 
	int leftend=rootIn-1;  //左子树在中序遍历的结束位置
	//cout<<leftrootPo<<" "<<leftstart<<" "<<leftend<<endl;
	
	int rightrootPo=rootPo-1; 
	int rightstart=rootIn+1;
	int rightend=end;
	//cout<<rightrootPo<<" "<<rightstart<<" "<<rightend<<endl;
	
	pre(leftrootPo,leftstart,leftend);  //递归左子树 
	pre(rightrootPo,rightstart,rightend);  //递归右子树 
}