105. Construct Binary Tree from Preorder and Inorder Traversal

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

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

/**
 * 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[] preorder, int[] inorder) {

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

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

    private TreeNode build(int[] preorder, int ps, int pe, int[] inorder, int is, int ie ){
        if(ps > pe || is > ie){
            return null;
        }

        TreeNode root = new TreeNode(preorder[ps]);
        int mid = map.get(preorder[ps]);
        int count = mid - is;
        root.left = build(preorder, ps+1, ps+count, inorder, is, mid - 1);
        root.right = build(preorder, ps+count+1, pe, inorder, mid+1, ie);

        return root;

    }
}