算法题–重建二叉树

6

要求

时间限制：1秒 空间限制：32768K

题目描述

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

解题思路

解题的前提：两个序列中必须有一个中序序列

前（后）序序列用于提供根节点，根节点就是序列第一个元素（最后一个元素）

中序序列用于确定当前根节点的左右子树有哪些节点

如下图所示：

确定了左右子树有哪些元素之后就继续递归

代码

/*Definition for binary treestruct 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)  {    int psize=pre.size();    int vsize=vin.size();          if(psize==0 || vsize==0 || psize != vsize)      return NULL;          return reBuildBinaryTreeCore(pre, 0, psize-1, vin, 0, vsize-1);  }    TreeNode* reBuildBinaryTreeCore(vector& pre, int startIdxOfP, int endIdxOfP,                                  vector& vin, int startIdxOfV, int endIdxOfV)  {    int valOfRoot = pre[startIdxOfP];    TreeNode* root = new TreeNode(valOfRoot);        if(startIdxOfP == endIdxOfP)    {      if(startIdxOfV == endIdxOfV)        return root;      else      {        cout << "无效输入" << endl;  abort();      }    }    else    {      int idxOfRootInV = 0;      for(idxOfRootInV = startIdxOfV;idxOfRootInV <= endIdxOfV &&           vin[idxOfRootInV] != valOfRoot;++idxOfRootInV)      {      }      if(vin[idxOfRootInV] != valOfRoot)      {        cout << "无效输入" << endl;        abort();      }          int leftLength = idxOfRootInV - startIdxOfV;      //左      if(startIdxOfV left = reBuildBinaryTreeCore(pre,                                           startIdxOfP + 1,                                           startIdxOfP + leftLength,                                           vin,                                           startIdxOfV,                                           idxOfRootInV - 1);      //右      if(idxOfRootInV + 1 right = reBuildBinaryTreeCore(pre,                                            startIdxOfP + 1 + leftLength,                                            endIdxOfP,                                            vin,                                            idxOfRootInV+1,                                            endIdxOfV);    }        return root;  }};

由于还要搬砖，没有办法一一回复私信把学习资料发给大家。我直接整理出来放在下面，觉得有帮助的话可以下载下来用于学习
链接：https://pan.baidu.com/s/1C-9TE9ES9xrySqW7PfpjyQ 提取码：cqmd

感谢各位人才的点赞、收藏、关注

微信搜「三年游戏人」收获一枚有情怀的游戏人，第一时间阅读最新内容，获取优质工作内推