题目描述

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

我的代码：

1 class Solution { 2 public: 3      TreeNode* reConstructBinaryTree(vector
     
       pre,vector
      
        vin) { 4           if(pre.empty() || vin.empty()) 5              return NULL; 6          TreeNode* pRoot = new TreeNode(pre[0]); 7          vector
       
         vleft,vright,pleft,pright; 8          int len = vin.size(); 9          int i = 0;10          for(; i < len; i++)11          {12              if(vin[i] == pRoot->val)13                  break;14              vleft.push_back(vin[i]);15              pleft.push_back(pre[i+1]);16         }//i的个数为 该跟的左子树17          for(int j = i+1; j < len; j++)18          {19              vright.push_back(vin[j]);20              pright.push_back(pre[j]);21          }22          pRoot->left = reConstructBinaryTree(pleft,vleft);23          pRoot->right = reConstructBinaryTree(pright,vright);24          return pRoot;25     }26 };
       
      
     

思路：前序遍历的第一个节点一定是根节点，在中序遍历中找到这个节点，左边的为左子树，右边的为右子树。

将左子树的前序和中序传入函数返回的值为根的左孩子

将右子树的前序和中序传入参数返回的值为根的右孩子

这样递归的找，就会重建成二叉树。