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

给定两个整数数组 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?=?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 库，那就写出极致性能的代码，可读性可以适当妥协。但这要求你花费更多时间去编写代码，且需要有足够的测试用例来保证正确性。

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

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