题目描述：
· 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
解题思路：
根据前序的第一个数字pre[0]是根的特性，再在中序中找到pre[0]在中序中的索引idx，分开，左边的是左子树，右边的是右子树。然后递归求出结果。
代码实现
思路1：
/**
* 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<int> pre,vector<int> vin) {
//递归终止条件
if(!pre.size()){
return nullptr;
}
vector<int> lef_pre,lef_vin;
vector<int> rig_pre,rig_vin;
TreeNode *head=new TreeNode(pre[0]);
//找到根节点
size_t idx=-1;
for(size_t i=0;i<vin.size();i++)
{
if(vin[i]==pre[0]){
idx=i;
break;
}
}
if(idx == -1){
return nullptr;
}
//树的根节点
head->val = vin[idx];
//左子树的前序中序
for(size_t i=0;i<idx;i++){
lef_pre.push_back(pre.at(i+1));
lef_vin.push_back(vin.at(i));
}
//右子树的前序中序
for(size_t i=idx+1;i<pre.size();i++){
rig_pre.push_back(pre.at(i));
rig_vin.push_back(vin.at(i));
}
//递归重建树的左右子树
head->left=reConstructBinaryTree(lef_pre,lef_vin);
head->right=reConstructBinaryTree(rig_pre,rig_vin);
return head;
}
};
