本文共 1492 字，大约阅读时间需要 4 分钟。

题目描述

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

思路

书上直接给的代码有点看不懂，递归这一块理解还是略差。

基本思路同书上思路，前序的第一个是根节点，这样在中序里面可以找到根，然后中序由根一分为二，前序中也可以知道根后面多少个是左子树（中序左边的个数），左边和右边继续重复上述做法。

代码

/** * Definition for binary tree * 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) {
     
if(pre.size() == 0 || vin.size() == 0)
     
return NULL;
     
else
     
return Construct(pre,vin);
     
}
     
TreeNode* Construct(vector
     
       pre,vector
      
        vin){
       
int len = pre.size();
       
if(len == 0){
       
return NULL;
       
}
       
vector
       
         preRight,preLeft,inRight,inLeft;
        
TreeNode* head = new TreeNode(pre[0]);
        
//找到前序第一个在中序的位置
        
int index=0;
        
for(int i = 0;i < len;i++){
        
if(vin[i] == pre[0]){
        
index = i;
        
break;
        
}
        
}
        
//左边的子树
        
for(int i = 0;i < index;i++){
        
preLeft.push_back(pre[i + 1]);
        
inLeft.push_back(vin[i]);
        
}
        
//右边的子树
        
for(int i = index+1;i < len;i++){
        
preRight.push_back(pre[i]);
        
inRight.push_back(vin[i]);
        
}
        
head->left=reConstructBinaryTree(preLeft,inLeft);
        
head->right=reConstructBinaryTree(preRight,inRight);
        
return head;
        
}
        
};
       
      
     
    
   

转载地址：https://blog.csdn.net/hanmin822/article/details/105417061 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！