106. Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

same as previous one.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for(int i = 0; i< inorder.length; i++){
            map.put(inorder[i], i);
        }    

        return build(inorder, 0, inorder.length-1, postorder, 0, postorder.length -1);
    }

    private TreeNode build(int[] inorder, int i0, int i1, int[] postorder, int p0, int p1){

        if(i0 > i1 || p0 > p1) return null;

        TreeNode root = new TreeNode(postorder[p1]);

        int mid = map.get(postorder[p1]);
        int count = i1 -mid; // right sub-tree size
        root.left = build(inorder, i0, mid-1, postorder, p0, p1 - count-1);
        root.right = build(inorder, mid+1, i1, postorder, p1-count, p1-1);

        return root;
    }
}