专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
秋招已经接近尾声，互联网大厂目前就了，据说有的开的比要的还多，除了美团其他大厂都还没开奖。校招对于即将毕业的大学生或者研究生来说是非常重要的，如果错过了，到毕业之后就只能参加社招了，这个难度要比校招大的多，所以即将毕业的学生一定要把握住。
最近一网友在投递小米岗位的时候被告知发错信息了，这个有可能是真的发错了，也有可能是招聘关闭了，所以在毕业之前就尽量把工作找好。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第105题：从前序与中序遍历序列构造二叉树。
问题描述
来源：LeetCode第105题
难度：中等
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例1：
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
示例2：
输入: preorder = [-1], inorder = [-1] 输出: [-1]
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均无重复元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列
问题分析
我们经常会对一棵二叉树进行前序和中序遍历，但这题让我们从前序与中序数组来构建二叉树。这题解法是比较多的，我们这里来看一种非常简单的解决方式。
我们知道二叉树 前序数组的第一个元素一定是根节点 ，因为前序遍历的顺序是先遍历根节点在遍历左右子树。而 中序遍历是根节点的左子树都遍历完了才遍历根节点 ，所以在中序数组中，根节点前面的元素是他的左子树节点，后面的元素是他右子树的节点。
根据这个特性我们可以把中序数组和前序数组划分两部分，然后每部分继续按照上面的方法划分，直到只有一个节点，不能划分为止。比如示例 1 的数组划分如下图所示。
划分的时候我们没必要把数组进行截取，只需要使用几个变量分别记录下前序和中序数组的区间范围即可。因为我们是根据前序数组中的元素在中序数组中的位置来划分中序数组的，所以这里只需要记录中序数组的范围，前序数组只需要记录起始位置即可。
JAVA：
public TreeNode buildTree(int[] preorder, int[] inorder) { // 为了方便后续进行查找，先把中序数组的所有值存储到map中 Map
map = new HashMap<>(); int length = inorder.length; for ( int i = 0; i < length; i++) map.put(inorder[i], i); return build(preorder, map, 0, 0, length - 1); } private TreeNode build(int[] preorder, Map map, int preStart, int inStart, int inEnd) { if (inStart > inEnd) return null; // 表示数组被访问完了。 // 使用前序数组的第一个元素创建根节点 TreeNode root = new TreeNode(preorder[preStart]); // 查找根节点在中序数组中位置 int index = map.get(root.val); int leftCount = index - inStart; // 左子树的所有节点个数 // 前序数组区间划分： // [preStart, preStart]根节点 // [preStart + 1, preStart + leftCount]左子树 // [preStart + leftCount + 1, ……]右子树 // 中序数组区间划分： // [inStart, index - 1]左子树 // [index, index]根节点 // [index + 1, inEnd]右子树 root.left = build(preorder, map, preStart + 1, inStart, index - 1); root.right = build(preorder, map, preStart + leftCount + 1, index + 1, inEnd); return root; }C++：
public: TreeNode *buildTree(vector
&preorder, vector
&inorder) { // 为了方便后续进行查找，先把中序数组的所有值存储到map中 unordered_map
m; int length = inorder.size(); for (int i = 0; i < length; i++) m[inorder[i]] = i; return build(preorder, m, 0, 0, length - 1); } TreeNode *build(vector
&preorder, unordered_map
&m, int preStart, int inStart, int inEnd) { if (inStart > inEnd) return nullptr;// 表示数组被访问完了。 // 使用前序数组的第一个元素创建根节点 TreeNode *root = new TreeNode(preorder[preStart]); // 查找根节点在中序数组中位置 int index = m[root->val]; int leftCount = index - inStart;// 左子树的所有节点个数 // 前序数组区间划分： // [preStart, preStart]根节点 // [preStart + 1, preStart + leftCount]左子树 // [preStart + leftCount + 1, ……]右子树 // 中序数组区间划分： // [inStart, index - 1]左子树 // [index, index]根节点 // [index + 1, inEnd]右子树 root->left = build(preorder, m, preStart + 1, inStart, index - 1); root->right = build(preorder, m, preStart + leftCount + 1, index + 1, inEnd); return root; }
Python：
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: def build(preStart: int, inStart: int, inEnd: int): if inStart > inEnd: return None # 表示数组被访问完了。 # 使用前序数组的第一个元素创建根节点 root = TreeNode(preorder[preStart]) # 查找根节点在中序数组中位置 index = m[root.val] leftCount = index - inStart # 左子树的所有节点个数 ''' 前序数组区间划分： [preStart, preStart]根节点 [preStart + 1, preStart + leftCount]左子树 [preStart + leftCount + 1, ……]右子树 中序数组区间划分： [inStart, index - 1]左子树 [index, index]根节点 [index + 1, inEnd]右子树 ''' root.left = build(preStart + 1, inStart, index - 1) root.right = build(preStart + leftCount + 1, index + 1, inEnd) return root # 为了方便后续进行查找，先把中序数组的所有值存储到map中 m = {element: i for i, element in enumerate(inorder)} return build(0, 0, len(preorder) - 1)笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴