题解 | #重建二叉树#

重建二叉树：最直观的想法是，前序数组pre，中序数组vin，首先判断pre数组的大小，如果为0则返回null，如果为1则返回构造节点pre[0]，否则第一步将pre的第一个元素pre[0]构造为当前根节点，第二步在中序数组中找到pre[0]对应的下标k，第三步根据k来划分中序数组的前半部分和后半部分，第四步根据中序数组的前半部分大小划分前序数组的前半部分和后半部分，第五步使用前序数组的前半部分和中序数组的前半部分找到当前根节点的左孩子，第六步使用前序数组的后半部分和中序数组的后半部分找到当前根节点的右孩子，最后返回当前根节点。

TreeNode* dfs(vector<int> &pre,vector<int> &vin)
{
   if(pre.size()==0) return nullptr;
   if(pre.size()==1) return new TreeNode(pre[0]);
   int kval=pre[0],k; //前序枢纽值 前序枢纽在中序的下标
   TreeNode *root=new TreeNode(kval);
   for(int i=0;i<vin.size();i++)
   {
      if(vin[i]==kval)
      {
        k=i;
        break;
      }
    }
    vector<int> vinl=vector<int>(vin.begin(),vin.begin()+k); //中序左半部分
    vector<int> vinr=vector<int>(vin.begin()+k+1,vin.end()); //中序右半部分
    vector<int> prel=vector<int>(pre.begin()+1,pre.begin()+1+vinl.size()); //前序左半部分
    vector<int> prer=vector<int>(pre.begin()+1+vinl.size(),pre.end()); //前序右半部分
    root->left=dfs(prel,vinl);
    root->right=dfs(prer,vinr);
    return root;
}
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) 
{
    if(pre.size()==0) return nullptr;
    return dfs(pre,vin);
}

优化：上述递归传递的参数只有前序数组和中序数组，并且在每一次递归过程中都创建了四个数组，分别是前序数组前半部分、前序数组后半部分、中序数组前半部分、中序数组后半部分，因为每次子数组都是在原有数组的基础上进行拆分的，所以如果我们可以考虑传递数组以及数组的起始和终止范围，那么可以大大优化空间。

TreeNode* dfs(vector<int> &pre,vector<int> &vin,int prel,int prer,int vinl,int vinr)
{
   if(prel>prer) return nullptr;
   if(prer==prel) return new TreeNode(pre[prel]);
   int kval=pre[prel],k; //前序枢纽值 前序枢纽在中序的下标
   TreeNode *root=new TreeNode(kval);
   for(int i=vinl;i<=vinr;i++)
   {
      if(vin[i]==kval)
      {
         k=i;
         break;
      }
    }
    root->left=dfs(pre,vin,prel+1,prel+1+(k-vinl)-1,vinl,k-1);
    root->right=dfs(pre,vin,prel+1+(k-vinl),prer,k+1,vinr);
    return root;
}
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) 
{
    if(pre.size()==0) return nullptr;
    return dfs(pre,vin,0,pre.size()-1,0,vin.size()-1);
}