``````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
/ \
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;
}
};``````