【西瓜哥说算法】从前序与中序遍历序列构造二叉树

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

给定两个整数数组 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 题目地址：

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

思路

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

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

它的前序遍历为：[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 库，那就写出极致性能的代码，可读性可以适当妥协。但这要求你花费更多时间去编写代码，且需要有足够的测试用例来保证正确性。

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

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