大家好，我是前端西瓜哥。今天我们来讲一道有点难度的二叉树算法题：从前序与中序遍历序列构造二叉树。

给定两个整数数组 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]

LeetCode 题目地址：

思路

这题的核心在于利用好二叉树的前序遍历和中序遍历特性。

让我们看看示例里的这个二叉树。

它的前序遍历为：[3,9,20,15,7]

中序遍历为：[9,3,15,20,7]

前序遍历的特点是先访问根节点，再访问左节点和右节点。所以前序遍历数组中，第一个元素就是整棵树的根节点。

前序遍历去掉首个元素后的剩余节点，其实可以找到某个索引位置，将这些节点分割，分割后左侧为左节点集合，右侧为右节点集合。

再看中序遍历，中序遍历什么特点。中序遍历遍历先访问左节点，再访问根节点，最后访问右节点。

前面我们通过前序遍历知道根节点是什么了，然后我们在中序遍历中找到这个根节点位置。

此时根节点位置的左侧就是根节点的左子树的所有节点（因为中序遍历 左->根->右 的特性），此时我们也可以计算出左子树的数量。

得到左子树数量，我们再回到前序遍历中，就能计算出左子树的子数组。

这里我们得到了左子树的前序遍历数组和中序遍历数组。

诶，这不是可以套娃了吗，接下来我们将这个两个数组再传入到递归函数中，递归就形成了。

右子树同理，这里就不赘述了。

代码实现

下面给大伙看看我的代码实现。

function buildTree(preorder, inorder) {  if (preorder.length === 0) return null;  const first = preorder[0];  const root = new TreeNode(first);  // 根节点在中序遍历中的位置  const idx = inorder.indexOf(first);  root.left = buildTree(    preorder.slice(1, idx + 1),    inorder.slice(0, idx)  );  root.right = buildTree(    preorder.slice(idx + 1),    inorder.slice(idx + 1)  );  return root;};

每次我们找到中序遍历中根节点的位置 idx，找到数组的切割位置。分别对 preorder 和 inorder 进行切割，找到左子树和右子树各自的前序遍历和中序遍历数组，然后接着递归。递归结束条件为数组为空。

这种实现的优点是可读性好，不容易写错。

但从效率上，它可以更好，有两个地方可以改进：

每次都要拷贝旧数组生成一个新数组，其实这里我们可以通过维护两对数组开头和结束索引来避免拷贝每次都要遍历 inorder 数组，来找出根节点的位置，效率较低。这点可以用哈希表缓存值到索引的映射。

我并不喜欢这种极致的优化导致的可读性下降。不过我还是得和你们说说优化思路的。

用了这两个方案后，我就要用一个新的递归函数了，因为参数变了。在这里，你可以给递归函数_buildTree 或 MyBuildTree 或者 f（函数的意思）、r（递归的意思）。

这里的命名我都不满意，我还是想用 buildTree。要是 JavaScript 也支持 Java 的那种真正的多态写法就好。Java Script 你这个冒牌 Java。

function buildTree(preorder, inorder) {  const map = {};  for (let i = 0; i < inorder.length; i++) {    map[inorder[i]] = i;  }  return _buildTree(preorder, inorder, map, 0, preorder.length, 0, inorder.length);};function _buildTree(preorder, inorder, map, pL, pR, iL, iR) {  if (pL >= pR) return null;  const first = preorder[pL];  const root = new TreeNode(first);  const idx = map[first];  const leftSize = idx - iL;  root.left = _buildTree(    preorder, inorder, map,    pL + 1, pL + 1 + leftSize,    iL, iL + leftSize  );  root.right = _buildTree(    preorder, inorder, map,    pL + leftSize + 1, pR,    idx + 1, iR  );  return root;};

这种实现的递归函数参数非常多，眼花缭乱，而且计算索引时也非常容易写错，但相比第一种实现确实运行效率更高。

结尾

代码是写给人看的，不是写给机器看的，只是顺便计算机可以执行而已。

在可读性和性能上，我们需要根据场景进行权衡。

如果是业务逻辑代码，对性能没有极致的要求，请写给人看的代码，可读性优先。

如果是底层的注重性能的非业务代码，比如像是 C++ 的 STL 库，那就写出极致性能的代码，可读性可以适当妥协。但这要求你花费更多时间去编写代码，且需要有足够的测试用例来保证正确性。

如果你去面试做算法题，不要强求自己一次写出完美的最佳实现。写出第一版后，再在原来的基础上一点点优化。面试官想要考察你的代码优化能力和思考。

我是前端西瓜哥，欢迎关注我。