题目描述

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

 

struct TreeNode{ 	int val;	TreeNode* left;	TreeNode* right;	TreeNode(int x):val(x),left(NULL),right(NULL){} };  class Solution{public:	TreeNode* reConstructBinaryTree(vector
     
       pre,vector
      
        vin) { 		TreeNode* root=reConstructBinaryTreeOne(pre,0,pre.size()-1,vin,0,vin.size()-1);		return root;	} 	//前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}private:	TreeNode* reConstructBinaryTreeOne(vector
       
         pre,int startPre,int endPre,vector
        
          vin,int startIn,int endIn) { 		if(startPre>endPre||startIn>endIn)			return nullptr;		TreeNode* root=new TreeNode(pre[startPre]); 		for(int i=startIn;i<=endIn;i++)			if(vin[i]==pre[startPre]){				root->left=reConstructBinaryTreeOne(pre,startPre+1,startPre+i-startIn,vin,startIn,i-1);				root->right=reConstructBinaryTreeOne(pre,i-startIn+startPre+1,endPre,vin,i+1,endIn);				break;			} 			return root;	}};
        
       
      
     

 

恭喜你通过本题

运行时间：8ms

占用内存：700