Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

记得考研的时候学习数据结构，经常会遇到根据某两种序列求另一种序列，当然并非已知两种遍历序列都可以求解第三种遍历序列。我们先分析下手动求解中序序列的方法：
例子：
preorder 前序 {3,9,20,15,7}
inorder 中序 {9,3,15,20,7}
前序中第一个元素3，因此在后续中3之前的数据为3的左孩子（此例中只有结点9，因此根结点的左孩子是9），3之后的是其右孩子，接下来在前序遍历中找到20，此时后续遍历中仅剩15 20 7，可以判定15是20的左结点，7是20的右结点。因此二叉树结构如下：
3
/ \
9 20
/ \
15 7

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        int rootInex = 0;
        return helper(preorder, rootInex, inorder, 0, inorder.size() - 1);
    }
    
private:
    TreeNode* helper(vector<int>& preorder, int& rootIndex, vector<int>& inorder, int start, int end) 
    {
        if(rootIndex >= preorder.size() || start > end) 
            return nullptr;
      // tree        [3,9,20,null,null,15,7]
     // preorder    [3,9,20,15,7]
     // inorder     [9,3,15,20,7]
    // 每次从 preorder 头部取一个值 preorder[rootIndex]，作为树的根节点
    // 检查 preorder[rootIndex] 在 inorder 中 的位置，则preorder[rootIndex]前面部分将作为树的左子树，右部分作为树的右子树
        TreeNode* root = new TreeNode(preorder[rootIndex]);
        auto pos = distance(inorder.begin(), find(inorder.begin() + start , inorder.begin() + end,preorder[rootIndex++]));
        root->left  = helper(preorder, rootIndex, inorder, start, pos - 1);
        root->right = helper(preorder, rootIndex, inorder, pos + 1, end);
        return root;
    }
};