关于javascript:JavaScript剑指offer-07重建二叉树

原题

输出某二叉树的前序遍历和中序遍历的后果，构建该二叉树并返回其根节点。假如输出的前序遍历和中序遍历的后果中都不含反复的数字。
credit to Leetcode

思路

先温习下 前序遍历 和中序遍历，对于图中的案例咱们能失去：

前序：[根，左，右] => [3, 9, 20, 15, 7]

中序：[左，根，右] => [9, 3, 15, 20, 7]

最重要的点在于理清思路，前序与中序的法则

前序首位就是树根节点，而这个根结点在中序中，会呈现在任何地位，在这里不难发现，根结点【3】在中序遍历后果中有着不同寻常的意义：根结点【3】的右边，是左子树，根结点的左边是右子树。

返回到前序遍历中去，咱们也能够把根和两个子树在前序遍历后果中划分进去，为之后的递归做筹备，【3】【9】【20, 15, 7】

接着就是针对于左子树和右子树的递归过程，例如此处针对右子树，咱们能够再次履行步骤 1 中的办法，来确定该子树的根结点和两个子树，发现根结点是首位【20】，而后回到中序遍历中找到【20】的地位，发现原来的右子树，又能够分为两个子树，【15】【20】【7】，这时就全副遍历完了

算法设计

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

这里的 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
};

总结

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