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

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

这种题目一看到就属于完全无从下手的感觉，答案能看懂比较好理解，但是要自己想挺难。这类题应该是题量还没上去，还没产生模糊的“这类题大概是用这种思路、方法、模版来做”的大脑反应，还需要继续多练题多总结。

Construct Tree from given Inorder and Preorder traversals

我们来看一下两种树的遍历：
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F

In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences. By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and elements on right are in right subtree. So we know below structure now.

      A 
     / \
    /   \ 
 D B E   F C

We recursively follow above steps and get the following tree.

        A 
      /   \
     /     \
    B       C
   / \      / 
  /   \    /
 D     E  F

Algorithm: buildTree()

1. Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
2. Create a new tree node tNode with the data as picked element.
3. Find the picked element’s index in Inorder. Let the index be inIndex.
4. Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5. Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.6) return tNode.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int preIndex = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null){
            return null;
        }
        int len = preorder.length;
        return helper(preorder, inorder, 0,  len - 1);
    }
    
    private TreeNode helper(int[] preorder, int[] inorder, int start, int end){
        if (start > end){
            return null;
        }
        TreeNode tNode = new TreeNode(preorder[preIndex]);
        preIndex++;
        int inIndex = search(inorder, tNode.val, start, end);
        tNode.left = helper(preorder, inorder, start, inIndex - 1);
        tNode.right = helper(preorder, inorder, inIndex + 1, end);
        return tNode;
    }
    
    private int search(int[] inorder, int value, int start, int end){
        for (int i = start; i <= end; i++){
            if (inorder[i] == value){
                return i;
            }
        }
        return -1;
    }
    
    
}