[JavaScript]剑指offer|[JavaScript]剑指offer 07.重建二叉树 [JavaScript]剑指offer07.重建二叉树

原题
输入某二叉树的前序遍历和中序遍历的结果，构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
credit to Leetcode
思路

文章图片

先复习下前序遍历和中序遍历，对于图中的案例我们能得到：
【[JavaScript]剑指offer|[JavaScript]剑指offer 07.重建二叉树】前序：[根，左，右] => [3, 9, 20, 15, 7]
中序：[左，根，右] => [9, 3, 15, 20, 7]
最重要的点在于理清思路，前序与中序的规律
前序首位就是树根节点，而这个根结点在中序中，会出现在任何位置，在这里不难发现，根结点【3】在中序遍历结果中有着不同寻常的意义：根结点【3】的左边，是左子树，根结点的右边是右子树。
返回到前序遍历中去，我们也可以把根和两个子树在前序遍历结果中划分出来，为之后的递归做准备，【3】【9】【20, 15, 7】
接着就是针对于左子树和右子树的递归过程，例如此处针对右子树，我们可以再次实行步骤1中的方法，来确定该子树的根结点和两个子树，发现根结点是首位【20】，然后回到中序遍历中找到【20】的位置，发现原来的右子树，又可以分为两个子树，【15】【20】【7】，这时就全部遍历完了
算法设计

因为当我们每次从前序结果中找到一个新根结点时，都要返回中序遍历进行子树的划分，所以创建一个哈希表来存储每个节点的值和索引，方便递归时的索引查找，我们设索引为k
对于递归函数，我们可以新建一个recur，参数分别为，前序的根索引root，中序的左边界left，中序的右边界right，当left > right时，说明没法再创建下一个节点了，返回null
接下来是最关键的部分，如何对根结点的左子树和右子树分别进行递归运算，这里用一个表格来体现：

	前序：根索引	中序：左边界	中序：右边界
左子树	root + 1	left	k - 1
右子树	k - left + root + 1	k + 1	right

这里的k - left + root + 1实际上是左子树长度 + root + 1
编码实现

/** * Definition for a binary tree node. * function TreeNode(val) { *this.val = val; *this.left = this.right = null; * } */ /** * @param {number[]} preorder * @param {number[]} inorder * @return {TreeNode} */ var buildTree = function(preorder, inorder) { const dic = new Map() for (let i = 0; i < inorder.length; i++){ dic.set(inorder[i], i) } const recur = (root, left, right) => { if (left > right) return null const k = dic.get(preorder[root]) const node = new TreeNode(preorder[root]) node.left = recur(root + 1, left, k - 1) node.right = recur(k - left + root + 1, k + 1, right) return node } return recur(0,0,preorder.length - 1) //初始的前序遍历结果代入，root索引为0 };

总结
这个题对于初学树这个数据结构的我来说，难度不小，也花了很长的时间去理解，看了很多讲解，最后发现还是没有自己动手画理解的快，这个题的难点应该在于，对于两种树遍历结果的差异的理解，和对左右子树进行递归运算的思路理解