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

解题思路

从前序遍历和中序遍历的规则出发，<br />前序： 根->左->右<br />中序： 左->根->右

根据前序遍历规则 可知首个遍历的是根节点，我们可以去中序遍历中找到根结点，然后再确定在前序遍历中 左右子树 就可以还原出整个二叉树，每层递归相同原则，在中序遍历中找到根结点，确定前序遍历中的左子树右子树。

题解

unction buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    let inMap = new Map();
    for (let i = 0; i < inorder.length; i++) {
        inMap.set(inorder[i], i);
    }
    function myBuildTree(preorders, inorders, preLeft, preRight, inLeft, inRight) {
        if (preLeft > preRight || inLeft > inRight) {
            return null;
        }
        let pIdx = inMap.get(preorders[preLeft]);
        let root: any = new TreeNode(preorders[preLeft]);
        root.left = myBuildTree(preorders, inorders, preLeft + 1, pIdx - inLeft + preLeft, inLeft, pIdx - 1);
        root.right = myBuildTree(preorder, inorders, pIdx - inLeft + preLeft + 1, preRight, pIdx+1, inRight);
        return root;
    }
    return myBuildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
};