重建二叉树

#ifndef RECONSTRUCT_BINARY_TREE_H
#define RECONSTRUCT_BINARY_TREE_H
#include<iostream>
struct TreeNode{
	int val; 
	struct TreeNode *left; 
	struct TreeNode *right; 
}; 
struct TreeNode *reconstructBinaryTree(int *preorder,int *midorder,int length); 
struct TreeNode *reconstructCore(int *startPreorder,int *endPreorder,int *startMidorder,int *endMidorder); 

struct TreeNode *reconstructBinaryTree(int *preorder,int *midorder,int length){
	return reconstructCore(preorder,preorder+length-1,midorder,midorder+length-1); 
}
struct TreeNode *reconstructCore(
	int *startPreorder,int *endPreorder,
	int *startMidorder,int *endMidorder){ //这里是关键，传入的参数是当前前序、中序的起始位置

	int rootValue=*startPreorder; 
	struct TreeNode *root=new TreeNode;  //核心部分，构建一个节点
	root->val=rootValue; 
	root->left=root->right=NULL; 
	if(startPreorder==endPreorder){    
		if(startMidorder==endMidorder&&*startPreorder==*startMidorder){
			return root;                  //边界值的处理
		}else{
			throw("invalid input "); 
		}
	}
	int *iter; 
	int leftCount=0; 
	for(iter=startMidorder; iter!=endMidorder; iter++){
		if(*iter==rootValue){
			break; 
		}
		leftCount++; 
	}
	if(iter!=startMidorder&&iter!=endMidorder){ //如果左右子树不为空
		root->left=reconstructCore(startPreorder+1,startPreorder+leftCount,startMidorder,iter-1); 
		root->right=reconstructCore(startPreorder+leftCount+1,endPreorder,iter+1,endMidorder); 
	}
	if(iter==startMidorder&&iter!=endMidorder){ //如果左子树为空
		root->left=NULL; 
		root->right=reconstructCore(startPreorder+leftCount+1,endPreorder,iter+1,endMidorder);	
	}
	if(iter!=startMidorder&&iter==endMidorder){ //如果右子树为空
		root->left=reconstructCore(startPreorder+1,startPreorder+leftCount,startMidorder,iter-1); 
		root->right=NULL;
	}
	return root; 
}
void preorderPrint(struct TreeNode *root){
	if(root==NULL){
		return;
	}
	std::cout<<root->val<<std::endl; 
	preorderPrint(root->left); 
	preorderPrint(root->right); 
}
void midorderPrint(struct TreeNode *root){
	if(root==NULL){
		return; 	
	}
	preorderPrint(root->left); 
	std::cout<<root->val<<std::endl; 
	preorderPrint(root->right);
}
#endif 

int main(){
	int pre[8]={1,2,4,7,3,5,6,8}; 
	int mid[8]={4,7,2,1,5,3,8,6};
	struct TreeNode *root=reconstructBinaryTree(pre,mid,8); 
	/*std::cout<<root->left->val<<std::endl; 
	std::cout<<root->left->left->right->val<<std::endl; 
	std::cout<<root->left->left->val<<std::endl; 
	std::cout<<root->right->left->val<<std::endl; 
	std::cout<<root->right->right->val<<std::endl; 
	std::cout<<root->right->right->left->val<<std::endl; */
	
	preorderPrint(root); 
	midorderPrint(root); 
}