专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
一网友在面试快手之后，进度一直是录用评估，这都评估一个月了还没消息，结果该网友给邮件上的HR打电话询问情况，HR说她离职了。我以为这是个例，结果在评论区有很多网友都遇到这种情况。这又是什么套路？为什么秋招的HR都喜欢离职，难道对接的HR都是实习的？
如果遇到这种情况，继续投简历找工作就是了，不用等了，HR离职有可能是真的离职，也有可能是你面试没通过，又懒得发邮件，随便找个借口应付了事。就像之前找工作面试结束之后HR会说回去等通知，如果过了肯定会收到通知，如果没过就算等一百年也不会给你通知。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第106题：从中序与后序遍历序列构造二叉树。
问题描述
来源：LeetCode第106题
难度：中等
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树 。
示例1：
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出：[3,9,20,null,null,15,7]
示例2：
输入：inorder = [-1], postorder = [-1] 输出：[-1]
1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由 不同 的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历
问题分析
这题是让根据中序和后续遍历数组来还原二叉树，我们知道 二叉树后序数组的最后一个元素一定是根节点 ，因为后序遍历的顺序是先遍历左右子树在遍历根节点。而中序遍历是根节点的左子树都遍历完了才遍历根节点，所以在中序数组中，根节点前面的元素是他的左子树节点，后面的元素是他右子树的节点。
根据这个特性我们可以把中序数组和后序数组划分两部分，然后每部分继续按照上面的方法划分，直到只有一个节点，不能划分为止。比如示例 1 的数组划分如下图所示。
划分的时候我们没必要把数组进行截取，只需要使用几个变量分别记录下后序和中序数组的区间范围即可。因为我们是根据后序数组中的元素在中序数组中的位置来划分中序数组的，所以这里只需要记录中序数组的范围，后序数组只需要记录起始位置即可。
JAVA：
public TreeNode buildTree(int[] inorder, int[] postorder) { // 为了方便后续进行查找，先把中序数组的所有值存储到map中 Map
map = new HashMap<>(); int length = inorder.length; for ( int i = 0; i < length; i++) map.put(inorder[i], i); return build(postorder, map, length - 1, 0, length - 1); } private TreeNode build(int[] postorder, Map map, int postEnd, int inStart, int inEnd) { if (inStart > inEnd) return null; // 表示数组被访问完了。 // 使用后序数组的最后一个元素创建根节点 TreeNode root = new TreeNode(postorder[postEnd]); // 查找根节点在中序数组中位置 int index = map.get(root.val); int rightCount = inEnd - index; // 右子树的所有节点个数 // 后序数组区间划分： // [……, postEnd-rightCount-1]左子树 // [postEnd-rightCount, postEnd-1]右子树 // [postEnd, postEnd]根节点 // 中序数组区间划分： // [inStart, index - 1]左子树 // [index, index]根节点 // [index + 1, inEnd]右子树 root.left = build(postorder, map, postEnd - rightCount - 1, inStart, index - 1); root.right = build(postorder, map, postEnd - 1, index + 1, inEnd); return root; }C++：
public: TreeNode *buildTree(vector
&inorder, vector
&postorder) { // 为了方便后续进行查找，先把中序数组的所有值存储到map中 unordered_map
m; int length = inorder.size(); for (int i = 0; i < length; i++) m[inorder[i]] = i; return build(postorder, m, length - 1, 0, length - 1); } TreeNode *build(vector
&postorder, unordered_map
&m, int postEnd, int inStart, int inEnd) { if (inStart > inEnd) return nullptr;// 表示数组被访问完了。 // 使用后序数组的第一个元素创建根节点 TreeNode *root = new TreeNode(postorder[postEnd]); // 使用后序数组的最后一个元素创建根节点 int index = m[root->val]; int rightCount = inEnd - index;// 右子树的所有节点个数 // 后序数组区间划分： // [……, postEnd-rightCount-1]左子树 // [postEnd-rightCount, postEnd-1]右子树 // [postEnd, postEnd]根节点 // 中序数组区间划分： // [inStart, index - 1]左子树 // [index, index]根节点 // [index + 1, inEnd]右子树 root->left = build(postorder, m, postEnd - rightCount - 1, inStart, index - 1); root->right = build(postorder, m, postEnd - 1, index + 1, inEnd); return root; }
Python：
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]: def build(postEnd: int, inStart: int, inEnd: int): if inStart > inEnd: return None # 表示数组被访问完了。 # 使用后序数组的最后一个元素创建根节点 root = TreeNode(postorder[postEnd]) # 查找根节点在中序数组中位置 index = m[root.val] rightCount = inEnd - index # 右子树的所有节点个数 ''' 后序数组区间划分： [……, postEnd-rightCount-1]左子树 [postEnd-rightCount, postEnd-1]右子树 [postEnd, postEnd]根节点 中序数组区间划分： [inStart, index - 1]左子树 [index, index]根节点 [index + 1, inEnd]右子树 ''' root.left = build(postEnd - rightCount - 1, inStart, index - 1) root.right = build(postEnd - 1, index + 1, inEnd) return root # 为了方便后续进行查找，先把中序数组的所有值存储到map中 m = {element: i for i, element in enumerate(inorder)} return build(len(postorder) - 1, 0, len(postorder) - 1)笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴