class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        List<Integer> pre = Arrays.stream(preorder).boxed().collect(Collectors.toList());
        List<Integer> in = Arrays.stream(inorder).boxed().collect(Collectors.toList());
        return buildTree(pre, in);
    }

    public TreeNode buildTree(List<Integer> preorder, List<Integer> inorder) {
        if (preorder.size() == 0) return null;
        int rootVal = preorder.get(0);
        int p = inorder.indexOf(rootVal);

        List<Integer> leftInorder = inorder.subList(0, p);
        List<Integer> rightInorder = inorder.subList(p + 1, inorder.size());
        List<Integer> leftPreorder = preorder.subList(1, p + 1);
        List<Integer> rightPreorder = preorder.subList(p + 1, preorder.size());

        TreeNode root = new TreeNode(rootVal);
        root.left = buildTree(leftPreorder, leftInorder);
        root.right = buildTree(rightPreorder, rightInorder);
        return root;
    }
}

class Solution {
    int indexOf(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) return i;
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        int rootVal = preorder[0];
        int p = indexOf(inorder, rootVal);
        int[] leftInorder = Arrays.copyOfRange(inorder, 0, p);
        int[] rightInorder = Arrays.copyOfRange(inorder, p + 1, inorder.length);
        int[] leftPreorder = Arrays.copyOfRange(preorder, 1, p + 1);
        int[] rightPreorder = Arrays.copyOfRange(preorder, p + 1, preorder.length);

        TreeNode root = new TreeNode(rootVal);
        root.left = buildTree(leftPreorder, leftInorder);
        root.right = buildTree(rightPreorder, rightInorder);
        return root;
    }
}