Binary Tree From Inorder And Postorder

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

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

Input : 
        Inorder : [2, 1, 3]
        Postorder : [2, 3, 1]

Return : 
            1
           / \
          2   3
Method:

The root is always the last one in postorder, then we need to determine what the left and right child.
By getting the root's index in inorder, we can know what is the left and right for in order and post order.

Solution:

Time: O(nlogn)
Space: O(n)

/**
 * Definition for binary tree
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {
 *      val = x;
 *      left=null;
 *      right=null;
 *     }
 * }
 */
public class Solution {
    public TreeNode buildTree(ArrayList<Integer> A, ArrayList<Integer> B) {
        if (A.size() == 0 || B.size() == 0) return null;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < A.size(); i ++) {
            map.put(A.get(i), i);
        }
        int rootVal = B.get(B.size() - 1);
        int rootInOrderIndex = map.get(rootVal);
        TreeNode root = new TreeNode(rootVal);
        root.left = buildTree(new ArrayList<>(A.subList(0, rootInOrderIndex)), new ArrayList<>(B.subList(0, rootInOrderIndex)));
        root.right = buildTree(new ArrayList<>(A.subList(rootInOrderIndex + 1, A.size())), new ArrayList<>(B.subList(rootInOrderIndex, B.size() - 1)));
        return root;
    }
}