[LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal

Problem : https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

The last number of postorder is the current root node value. Use the root node value to locate numbers belong to the left sub-tree and right sub-tree. Then construct binary tree recursively.

class Solution {
    static int[] memo = new int[6001];

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            memo[inorder[i]+3000] = i;
        }
        return helper(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    TreeNode helper(int[] inorder, int l1, int r1, int[] postorder, int l2, int r2) {
        if (l1 >= r1 || l2 >= r2) {
            return null;
        }

        // find root in inorder
        int pivot = memo[postorder[r2-1] + 3000];
       
        return new TreeNode(
            inorder[pivot],
            helper(inorder, l1, pivot, postorder, l2, l2 + pivot - l1),
            helper(inorder, pivot+1, r1, postorder, l2 + pivot - l1, r2-1));
    }
}