求star

题目#

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

题解:key:#

①递归#

TIP

对任意一棵树而言:

• 前序遍历: [根节点,[左子树前序遍历结果],[右子树前序遍历结果]]
• 中序遍历: [[左子树前序遍历结果],根节点,[右子树前序遍历结果]]

所以可以通过前序遍历确定根节点，然后在根据根节点在中序遍历中的位置确定左右子树的区间，最后通过递归构建子树

利用Map实现哈希表，避免每次查询根节点都要遍历一次数组，提高效率

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    const map = new Map()
    let preIndex = 0
    for(let i=0;i<inorder.length;++i) {
        map.set(inorder[i],i)
    }
    const myBuildTree = (left,right) => {
        if(left > right)    return null
        const root = new TreeNode(preorder[preIndex++])
        const iIndex = map.get(root.val);
        root.left = myBuildTree(left,iIndex-1);
        root.right = myBuildTree(iIndex+1,right);
        return root
    }
    return myBuildTree(0,preorder.length-1)
};