Question:

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

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

Thinking:

This question is similar with Construct Binary Tree from Inorder and Postorder Traversal. We should understand the differences and the sequences of these three methods. And divide into three parts- root, left child and right child.

Solution:

public TreeNode buildTree(int[] preorder, int[] inorder) {
    int l = preorder.length;
    if (l == 0)
        return null;


    return dp(preorder, inorder, 0, l-1, 0, l-1);
    }

    private TreeNode dp(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd){
    if (preStart > preEnd || preEnd >= preorder.length || inEnd >= preorder.length)
        return null;
    TreeNode root = new TreeNode(preorder[preStart]);
    int index = inStart;
    for (; index < inEnd; index++){
        if (inorder[index] == preorder[preStart])
            break;
    }

    TreeNode left = dp(preorder, inorder, preStart+1, preStart+index-inStart, inStart, index-1);
    TreeNode right = dp(preorder, inorder,preStart+index-inStart+1, preEnd, index+1, inEnd);
    root.left = left;
    root.right = right;

    return root;
}    

This method can be improved by using HashMap to make it faster when fiding the index of root.
Reference:http://blog.csdn.net/linhuanmars/article/details/24389549
Code:

static HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
    int l = preorder.length;
    if (l == 0)
        return null;
    for (int i = 0; i < l; i++)
        map.put(inorder[i], i);

    return dp(preorder, inorder, 0, l-1, 0, l-1);
}

private TreeNode dp(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd){
    if (preStart > preEnd || inStart > inEnd)
        return null;
    TreeNode root = new TreeNode(preorder[preStart]);

    int index = map.get(preorder[preStart]);

    TreeNode left = dp(preorder, inorder, preStart+1, preStart+index-inStart, inStart, index-1);
    TreeNode right = dp(preorder, inorder,preStart+index-inStart+1, preEnd, index+1, inEnd);
    root.left = left;
    root.right = right;

    return root;
}