【西瓜哥说算法】从前序与中序遍历序列构造二叉树
大家好，我是前端西瓜哥。今天我们来讲一道有点难度的二叉树算法题：从前序与中序遍历序列构造二叉树。
给定两个整数数组 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]
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 库，那就写出极致性能的代码，可读性可以适当妥协。但这要求你花费更多时间去编写代码，且需要有足够的测试用例来保证正确性。
如果你去面试做算法题，不要强求自己一次写出完美的最佳实现。写出第一版后，再在原来的基础上一点点优化。面试官想要考察你的代码优化能力和思考。
我是前端西瓜哥，欢迎关注我。