#include <iostream>
#include <vector>
using namespace std;

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

void printTree(TreeNode *T){
	if(T!=NULL){
		cout<<T->val<<" ";
		printTree(T->left);
		printTree(T->right);
	}
}

void binaryTree(vector<int> pre,vector<int> in,TreeNode *parent,int lr){
	int s=pre.size();
	if(s>0){                                               //非空
		int nodeData=pre.front();
		TreeNode *root=new TreeNode(nodeData);
		if(lr==0)
			parent->left=root;
		else
			parent->right=root;
		int i;
		for(i=0;i<in.size();i++){
			if(in[i]==nodeData)
				break;
		}
		vector<int> Lpre(pre.begin()+1,pre.begin()+i+1);
		vector<int> Rpre(pre.begin()+i+1,pre.end());
	
		vector<int> Lin(in.begin(),in.begin()+i);
		vector<int> Rin(in.begin()+i+1,in.end());
	
		binaryTree(Lpre,Lin,root,0);
		binaryTree(Rpre,Rin,root,1);
	}
}

struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in){
	int s=pre.size();
	if(s>0){                                                  //非空
		 int nodeData=pre.front();
		 TreeNode *root=new TreeNode(nodeData);
		 int i;
		 for(i=0;i<in.size();i++){
			 if(in[i]==nodeData)
				 break;
		 }
		 vector<int> Lpre(pre.begin()+1,pre.begin()+i+1);
		 vector<int> Rpre(pre.begin()+i+1,pre.end());
	
		 vector<int> Lin(in.begin(),in.begin()+i);
		 vector<int> Rin(in.begin()+i+1,in.end());
	
		 binaryTree(Lpre,Lin,root,0);
		 binaryTree(Rpre,Rin,root,1);
		 return root;
	}else
		return NULL;
}

int main(){
	int a1[8]={1,2,4,7,3,5,6,8};
	int a2[8]={4,7,2,1,5,3,8,6};
	vector<int> pre(a1,a1+8);
	vector<int> in(a2,a2+8);
	TreeNode *r;
	r=reConstructBinaryTree(pre,in);
	printTree(r);
	system("pause");
}