106. 从中序与后序遍历序列构造二叉树 中等

问题：

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

回答：

可以类比第105道题，从前序与中序遍历序列构造二叉树

构造哈希表，存储中序遍历的节点和索引位置

后序是左右根，所以最后一个元素就是根节点，找到根节点后在哈希表中查找所在位置，根节点左侧为左子树，右侧为右子树

var buildTree = function(inorder, postorder) {
    let map = new Map();
    for (let i = 0; i < inorder.length; i++) {
        map.set(inorder[i], i);
    }
    var build = function(postStart, postEnd, inStart, inEnd) {
        if (postStart > postEnd || inStart > inEnd) {
            return null;
        }
        let rootVal = postorder[postEnd];
        let root = new TreeNode(rootVal);
        let rootIndex = map.get(rootVal);
        let leftSize = rootIndex - inStart;
        root.left = build(postStart, postStart + leftSize - 1, inStart, rootIndex - 1);
        root.right = build(postStart + leftSize, postEnd - 1, rootIndex + 1, inEnd);
        return root
    }
    return build(0, postorder.length - 1, 0, inorder.length - 1);
};