//输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。



struct TreeNode
{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x):val(x), left(NULL), right(NULL){}
};


void reConstructBinaryTreeFun(TreeNode *head, vector<int> pre, vector<int> vin)
{
	if(pre.size() <= 1 && vin.size() <=1)//没有子节点了，结束
	{
		return ;
	}

	vector<int> vecLeftVin, vecLeftPre;
	vector<int> vecRightVin, vecRightPre;
	size_t vecLeftVin_size = 0;
	vector<int>::iterator it;
	//前序遍历的第一个（即pre[0]）为根节点
	it = find(vin.begin(), vin.end(), pre[0]); //找到根节点在中序遍历中的位置
	head->val = pre[0];
	//中序遍历根节点左边的，为左分支。
	if(it != vin.begin())
	{
		head->left = new TreeNode( *(it-1) );//中序遍历中，根节点左边第一个为根的左节点。
		vecLeftVin.assign(vin.begin(),it);//将中序遍历中根左边的部分放到新的vec中
		vecLeftVin_size = vecLeftVin.size();//记录大小

		vecLeftPre.assign(pre.begin()+1, pre.begin()+1+vecLeftVin_size);//将前序遍历中根左边的部分放到新的vec中
		reConstructBinaryTreeFun(head->left,vecLeftPre, vecLeftVin);//继续递归分析

	}

	//中序遍历根节点右边的，为右分支。

	if(it != vin.end()-1)
	{
		head->right = new TreeNode( *(it+1));//中序遍历中，根节点右边第一个为根的右节点。
		vecRightVin.assign(it+1, vin.end()); //将中序遍历中根右边的部分放到新的vec中
		size_t vecRightVin_size = vecRightVin.size();//记录大小
		vecRightPre.assign(pre.end()-vecRightVin_size, pre.end());//将前序遍历中根右边的部分放到新的vec中
		reConstructBinaryTreeFun(head->right, vecRightPre, vecRightVin);//继续递归分析
	}

}


TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin)
{
	TreeNode * head ;
	head  = new TreeNode(pre[0]);

	reConstructBinaryTreeFun(head,pre,vin);

	return head;

}