Construct Binary Tree from Preorder and Inorder Traversal

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

Analysis

Similar to Construct Binary Tree from Inorder and Postorder Traversal

Code

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder==null || inorder==null || preorder.length!=inorder.length) {return null;}
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        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, map);
    }

    private TreeNode build(int[] pre, int ps, int pe, int[] in, int is, int ie, HashMap<Integer, Integer> map){
        if(ps>pe || is>ie) {return null;}
        int ri = map.get(pre[ps]);
        TreeNode root = new TreeNode(pre[ps]);
        TreeNode left = build(pre, ps+1, ps+ri-is, in, is, ri-1, map);
        TreeNode right = build(pre, ps+ri-is+1, pe, in, ri+1, ie, map);
        root.left = left;
        root.right = right;
        return root;
    }
}