假設已知先序序列為PRe₁,pre₂..pre_n，中序序列為in₁,in₂..in_n，如下圖所示，由先序序列的性質可知u，先序序列的第一個元素pre₁是當前二叉樹的根結點。再有中序序列的性質可知，當前二叉樹的根結點將中序序列劃分為左子樹和右子樹。因此只要在中序序列中找到某個結點in_k，使得in_k==pre₁，這樣就找到了根結點。易只左子樹的結點個數numLeft=k-1，從而左子樹先序序列的區間就是[2,k]，左子樹的中序序列區間就是[1,k-1]；右子樹的先序序列區間[k+1,n]，右子樹的中序序列區間[k+1,n]。

就一般性來說，如果遞歸過程中當前先序序列的區間為[preL,preR]，中序序列的區間為[inL,inR]。那么左子樹的結點個數numLeft=k-inL。這樣左子樹的先序序列的區間就是[preL+1,preL+numLeft]，左子樹的中序序列區間是[inL,k-1]；右子樹的先序序列區間是[preL+numLeft+1,preR]，右子樹的中序序列區間是[k+1,inR]。具體區間 可以參看下圖。

每一次遞歸都可以獲得對應子樹的根結點，那么遞歸的邊界在哪呢？很明顯只要先序序列的長度小于等于0時，二叉樹就不存在了。

比如給出的二叉樹如下圖所示：

先序遍歷：4 1 3 2 6 5 7

中序遍歷：1 2 3 4 5 6 7

后序遍歷：2 3 1 5 7 6 4

層次遍歷：4 1 6 3 5 7 2

先序&中序

定義結構如下：

const int M=100; //最大的節點數 int pre[M],in[M],post[M],lay[M],;//前、中、后、層次遍歷的序列 下標從1開始 int map[M];//保存層次遍歷序列的元素下標(元素過大,可以使用STL-map替換) struct Node{	int data;	Node *lchild ,*rchild;}; 
根據上面的分析，下面給出由先序和中序構建一棵二叉樹的代碼：
Node* create(int preL,int preR,int inL,int inR){  //初始create(1,n,1,n)	if(preL>preR){//遞歸邊界 		return NULL;	}	Node* root=new Node();	root->data=pre[preL];//保存當前root的值 	int k; //root在中序的下標 	for(k=inL;k<=inR;k++){		if(in[k]==pre[preL]){//在中序查找root 			break;		} 	}	int numLeft=k-inL;//獲得左子樹結點數目	//遞歸構建左子樹 	root->lchild=create(preL+1,preL+numLeft,inL,k-1); 	//遞歸構建右子樹 	root->rchild=create(preL+numLeft+1,preR,k+1,inR); 	return root; }
后序&中序
由后序和中序構建二叉樹。由后序遍歷的性質可知，最后一個元素為根結點，而中序序列的區間沒有改變，只需要修改上面代碼的先序部分即可，修改后的代碼如下：
Node* createByPostInOrder(int postL,int postR,int inL,int inR){	if(postL>postR){//遞歸邊界 		return NULL;	}	Node* root=new Node();	root->data=post[postR];//保存當前root的值 	int k; //root在中序的下標 	for(k=inL;k<=inR;k++){		if(in[k]==post[postR]){//在中序查找root 			break;		} 	}	int numLeft=k-inL;//獲得左子樹結點數目	//遞歸構建左子樹 修改了后序的區間部分	root->lchild=createByPostInOrder(postL,postL+numLeft-1,inL,k-1); 	//遞歸構建右子樹 	root->rchild=createByPostInOrder(postL+numLeft,postR-1,k+1,inR); 	return root; }
層次&中序
由層次遍歷的性質可知，在遞歸的過程中無法根據中序的根節點劃分出層次的左右子樹，但是層次遍歷保證了序列中最靠前的元素一定是當前的根結點。因此可以使用一個map保存層次遍歷元素的下標，若元素較小，可以直接使用數組保存。
for(int i=1;i<=n;i++){	cin>>lay[i];	map[lay[i]]=i; //保存map }每次根據當前的根結點劃分中序序列后，在子序列中找到在層次遍歷序列中最靠前的元素即為root，實現代碼如下：
Node* create(int inL,int inR){	if(inL>inR){//遞歸邊界 		return NULL;	}	Node* root=new Node();	int k=inL; //root在中序的下標 	for(int i=inL+1;i<=inR;i++){		if(map[k]>map[i]){//在當前中序序列查找其在層次遍歷中最靠前的元素 			k=i;     //最靠前的即是root 		} 	}	root->data=in[k];	int numLeft=k-inL;//獲得左子樹結點數目	//遞歸構建左子樹 	root->lchild=create(inL,k-1); 	//遞歸構建右子樹 	root->rchild=create(k+1,inR); 	return root; }