//输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 //例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。  1 作者：技术不宅 2 链接：https://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6 3 来源：牛客网 4  5 #include 
     
       6 #include 
      
        7 using namespace std; 8  9 10 struct TreeNode {11  int val;12  TreeNode *left;13  TreeNode *right;14  TreeNode(int x) : val(x), left(NULL), right(NULL) {}15 };16 17 struct TreeNode* reConstructBinaryTree(vector
       
         pre, vector
        
          in)18 {19  if (pre.size() == NULL)20   return NULL;21  TreeNode* root = new TreeNode(pre[0]);22  int i;23  for (i = 0; i < in.size() && in[i] != pre[0]; i++);24  vector
         
           pre_left, in_left,pre_right,in_right;25  int pre_i = 1;26  for (int j = 0; j < in.size(); j++)27  {28   if (j < i)29   {30    in_left.push_back(in[j]);31    pre_left.push_back(pre[pre_i]);32    pre_i++;33   }34   else if (j>i)35   {36    in_right.push_back(in[j]);37    pre_right.push_back(pre[pre_i]);38    pre_i++;39   }40  }41  root->left = reConstructBinaryTree(pre_left, in_left);42  root->right = reConstructBinaryTree(pre_right, in_right);43  return root;44 }45 46 int main()47 {48  vector
          
            pre = { 1, 2, 4, 7, 3, 5, 6, 8 };49  vector
           
             in = { 4, 7, 2, 1, 5, 3, 8, 6 };50  TreeNode* root= reConstructBinaryTree(pre, in);51  int a = 0;52 }