106. Construct Binary Tree from Inorder and Postorder Traversal

1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 *     val: number
5 *     left: TreeNode | null
6 *     right: TreeNode | null
7 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 *         this.val = (val===undefined ? 0 : val)
9 *         this.left = (left===undefined ? null : left)
10 *         this.right = (right===undefined ? null : right)
11 *     }
12 * }
13 */
14
15function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
16    const inorder_index: Map<number, number> = new Map();
17    inorder.forEach((val, idx) => inorder_index.set(val, idx))
18    let post_idx = postorder.length - 1;
19    function helper(left: number, right: number): TreeNode | null {
20	    if(left > right) return null;
21	    const root_val = postorder[post_idx--];
22	    const root = new TreeNode(root_val);
23	    const idx = inorder_idx.get(root_val);
24	    root.right = helper(idx + 1, right);
25	    root.left = helper(left, idx - 1);
26	    return root;
27	    
28    }
29    return helper(0, inorder.length - 1)
30};