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

function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
}


/**
 *
原理：
1.前序遍历(中左右)的根节点在第一位
2.后序遍历(左右中)的根节点在最后一位
3.中序遍历(左中右)的根节点在中间某个位置，并将结果分为左右两棵子树的中序遍历

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
首先根据 preorder 找到根节点是 3
    
然后根据根节点将 inorder 分成左子树和右子树
左子树
left_inorder [9]

右子树
right_inorder [15,20,7]

把相应的前序遍历的数组也加进来
左子树
left_preorder:[9] 等于preorder的 root_index+1 到 root_index+1+left_inorder.length 的区间
left_inorder: [9]

右子树
right_preorder:[20 15 7] 等于preorder的 root_index+left_inorder.length+1 到 末尾 的区间
right_inorder: [15,20,7]

现在我们只需要构造左子树和右子树即可，成功把大问题化成了小问题
然后重复上边的步骤继续划分，直到 preorder 和 inorder 都为空，返回 null 即可

 */

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
    // 递归结束条件
    if (preorder.length === 0) {
        return null
    }

    // 前序遍历结果的第一项就是根节点
    const rootVal = preorder[0]
    const root = new TreeNode(rootVal)

    // 根据root把中序遍历分为左右两棵子树
    let rootIndex
    for (let i = 0; i < inorder.length; i++) {
        if (inorder[i] === root.val) {
            rootIndex = i
            break
        }
    }

    const leftInorder = inorder.slice(0, rootIndex) // 左子树的中序遍历
    const rightInorder = inorder.slice(rootIndex + 1) // 右子树的中序遍历
    const leftPreorder = [] // 左子树的前序遍历
    const rightPreorder = [] // 右子树的前序遍历
    for (let i = 0; i < preorder.length; i++) {
        if (leftInorder.includes(preorder[i])) { // 左子树的节点
            leftPreorder.push(preorder[i])
            continue
        }
        if (rightInorder.includes(preorder[i])) { // 右子树的节点
            rightPreorder.push(preorder[i])
            continue
        }
    }

    // 继续往下构造左右子树
    root.left = buildTree(leftPreorder, leftInorder) // 左子树
    root.right = buildTree(rightPreorder, rightInorder) // 右子树

    return root
};

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
// 优化版本
var buildTree = function (preorder, inorder) {
    // 先用哈希表把inorder的值记录下来，key为inorder的值，value为下标，就不用每次递归都遍历一遍找根节点
    let inorderMap = {}
    for (let i = 0; i < inorder.length; i++) {
        inorderMap[inorder[i]] = i
    }

    // 递归构建树
    function build(preorderStartIndex, preorderEndIndex, inorderStartIndex, inorderEndIndex) {
        // 递归结束条件
        if (preorderStartIndex > preorderEndIndex) {
            return null
        }

        // 前序遍历第一个节点就是根节点
        const preorderRootIndex = preorderStartIndex
        // 在中序遍历中定位根节点
        const inorderRootIndex = inorderMap[preorder[preorderRootIndex]]

         // 创建根节点
        const root = new TreeNode(preorder[preorderRootIndex])

        // 得到左子树节点数目
        const leftSubTreeSize = inorderRootIndex - inorderStartIndex

        // 把inorder分成左右两棵子树
        const leftInorderStartIndex = inorderStartIndex // inorder左子树开始下标
        const leftInorderEndIndex = inorderRootIndex - 1 // inorder左子树结束下标
        const rightInorderStartIndex = inorderRootIndex + 1 // inorder右子树开始下标
        const rightInorderEndIndex = inorderEndIndex // inorder右子树结束下标

        // 根据root找出preorder的左右子树
        const leftPreorderStartIndex = preorderRootIndex + 1 // preorder左子树开始下标
        const leftPreorderEndIndex = (leftPreorderStartIndex + leftSubTreeSize) - 1 // preorder左子树结束下标
        const rightPreorderStartIndex = leftPreorderEndIndex + 1 // preorder右子树开始下标
        const rightPreorderEndIndex = preorderEndIndex // preorder右子树结束下标

        // 构建左右子树
        root.left = build(leftPreorderStartIndex, leftPreorderEndIndex, leftInorderStartIndex, leftInorderEndIndex)
        root.right = build(rightPreorderStartIndex, rightPreorderEndIndex, rightInorderStartIndex, rightInorderEndIndex)

        return root
    }

    let n = preorder.length
    return build(0, n - 1, 0, n - 1)
}