105. 从前序与中序遍历序列构造二叉树 中等

问题：

给定两个整数数组 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]

回答：

1.构造哈希表，存储中序遍历的每个元素的索引对应关系，先序遍历的第一个节点是根节点，找到根节点之后可以从哈希表中快速找到在中序遍历中根节点的位置

2.中序遍历，根节点左侧的所有元素为左子树，右侧的元素为右子树，然后递归调用左右子树来构造二叉树

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
function buildTree(preorder, inorder) {
    //构建哈希表，快速寻找根节点位置
    var map = new Map();
    for (let i = 0; i < inorder.length; i++) {
        map.set(inorder[i], i)
    }
    var build = function(preindex, preEnd, inindex, inEnd) {
        //终止条件,没有节点需要处理
        if (preindex > preEnd || inindex > inEnd) {
            return null;
        }
        //先序遍历的第一个元素就是根节点
        let rootval = preorder[preindex];
        let root = new TreeNode(rootval);
        //在中序遍历中找到根节点位置
        let rootIndex = map.get(rootval);
        //根节点左侧为左子树的节点数量
        let leftLen = rootIndex - inindex;
        root.left = build(preindex + 1, preindex + leftLen, inindex, rootIndex -1);
        root.right = build(preindex + leftLen + 1, preEnd, rootIndex + 1, inEnd);
        return root;
    }
    //返回最终构建的树
    return build(0, preorder.length - 1, 0, inorder.length - 1);
}