// 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 binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    	// some key ideas are that: 
    	// 1.first element of preorder is the root node.
    	// 2.if found the root node's index in the in-order array, 
    	//   then indexes smaller than it represents left sub-tree, indexes larger than the 
    	//   root index represent the right sub-tree.
    	// 3. each iteration we need to locate the root's index in in-order array.
    	int pLen = preorder.length;
    	int iLen = inorder.length;
    	if(pLen != iLen || pLen == 0) return null;

    	return helper(preorder, inorder, 0, pLen - 1, 0);
    }

    public TreeNode helper(int[] preorder, int[] inorder, int iStart, int iEnd, int pIndex){
    	if(iStart > iEnd) return null;
    	if(iStart == iEnd) return new TreeNode(inorder[iStart]);

    	int mid = 0;

    	for(int i = iStart; i <= iEnd; i++){
    		if(preorder[pIndex] == inorder[i]){
    			mid = i;
    			break;
    		}
    	}

    	TreeNode node = new TreeNode(inorder[mid]);
    	// why pIndex + 1: since in the preorder traversal, next element is the root of current
    	// element's left subtree.
    	node.left = helper(preorder, inorder, iStart, mid - 1, pIndex + 1);
    	// why mid - istart + 1: it represents all the elements covered so far, which are all
    	// less then the root node's value.
    	node.right = helper(preorder, inorder, mid + 1, iEnd, pIndex + (mid - iStart + 1));

    	return node;
    }
}

@@ -1782,8 +1782,1451 @@
     %7D%0A%7D%0A
+%0A%0A/**%0A * Definition for binary tree%0A * public class TreeNode %7B%0A *     int val;%0A *     TreeNode left;%0A *     TreeNode right;%0A *     TreeNode(int x) %7B val = x; %7D%0A * %7D%0A */%0Apublic class Solution %7B%0A    public TreeNode buildTree(int%5B%5D preorder, int%5B%5D inorder) %7B%0A        int len = preorder.length;%0A        if (len == 0) %7B%0A            return null;%0A        %7D%0A%0A        return buildHelper(preorder, inorder, 0, len - 1, 0, len - 1);%0A    %7D%0A%0A    public TreeNode buildHelper(int%5B%5D preorder, int%5B%5D inorder, int preStart, int preEnd, int inStart, int inEnd) %7B%0A        if (preStart %3E preEnd) %7B%0A            return null;%0A        %7D%0A%0A        TreeNode root = new TreeNode(preorder%5BpreStart%5D);%0A        int rootIndex = 0;%0A%0A        for (int i = inStart; i %3C= inEnd; i++) %7B%0A            if (inorder%5Bi%5D == preorder%5BpreStart%5D) %7B%0A                rootIndex = i;%0A                break;%0A            %7D%0A        %7D%0A%0A        int leftSize = rootIndex - inStart;%0A        int rightSize = inEnd - rootIndex;%0A        // inorder index range is easy: left : (inStart, rootIndex - 1),  right: (rootIndex + 1, inEnd)%0A        // preorder needs calculation. left: (preStart + 1, preStart + leftSize), right : (preEnd - rightSize + 1, preEnd)%0A        root.left = buildHelper(preorder, inorder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1);%0A        root.right = buildHelper(preorder, inorder, preEnd - rightSize + 1, preEnd, rootIndex + 1, inEnd);%0A%0A        return root;%0A    %7D%0A%7D%0A%0A%0A

update construct binary tree from preorder and inorder solution