Construct Binary Tree From Inorder And Preorder

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

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

Return :
            1
           / \
          2   3

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 < B.size(); i ++) {
            map.put(B.get(i), i);
        }
        int rootVal = A.get(0);
        int rootInOrderIndex = map.get(rootVal);
        TreeNode root = new TreeNode(rootVal);
        root.left = buildTree(new ArrayList<>(A.subList(1, rootInOrderIndex + 1)), new ArrayList<>(B.subList(0, rootInOrderIndex)));
        root.right = buildTree(new ArrayList<>(A.subList(rootInOrderIndex + 1, A.size())), new ArrayList<>(B.subList(rootInOrderIndex + 1, B.size())));
        return root;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return pre(preorder, inorder);
    }
    
    private TreeNode pre(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        Map<Integer, Integer> valToInOrderIndex = new HashMap();
        for (int i = 0; i < inorder.length; i ++) {
            valToInOrderIndex.put(inorder[i], i);
        }
        TreeNode root = new TreeNode(preorder[0]);
        int inorderIndex = valToInOrderIndex.get(root.val);
        root.left = pre(Arrays.copyOfRange(preorder, 1, 1 + inorderIndex), Arrays.copyOfRange(inorder, 0, inorderIndex));
        root.right = pre(Arrays.copyOfRange(preorder, 1 + inorderIndex, preorder.length), Arrays.copyOfRange(inorder, inorderIndex + 1, inorder.length));
        return root;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> valToInOrderIndex = new HashMap();
        for (int i = 0; i < inorder.length; i ++) {
            valToInOrderIndex.put(inorder[i], i);
        }
        return pre(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1, valToInOrderIndex);
    }
    
    private TreeNode pre(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd, Map<Integer, Integer> valToInOrderIndex) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        int inorderIndex = valToInOrderIndex.get(root.val);
        int leftSubTreeSize = inorderIndex - inStart;
        root.left = pre(preorder, inorder, preStart + 1, preStart + leftSubTreeSize, inStart, inorderIndex - 1, valToInOrderIndex);
        root.right = pre(preorder, inorder, preStart + leftSubTreeSize + 1, preEnd, inorderIndex + 1, inEnd, valToInOrderIndex);
        return root;
    }
}