[LeetCode]Construct Binary Tree from Preorder and Inorder Traversal

给定一棵树的先序遍历和中序遍历结果，重新构建这棵树。

解决思路：

1. 从先序遍历序列中找到root节点

2. 在中序遍历序列中找到root出现的下标位置，记为root_iter. root_iter左边的为左子树的中序遍历序列，长度为lTreeSize, 右边为右子树的中序遍历序列。

3. 先序遍历序列中，除了第一个元素root节点，剩下的lTreeSize个元素是左子树的先序遍历序列，最后剩下的就是右子树的中序遍历序列了。

4. 得到左右子树的先序，中序遍历序列后，递归构建左右子树。

编码上的坑：

vector的迭代器的end指向容器中最后一个元素的后一位，为一虚拟元素。左子树递归下标更新时需要注意。

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 
11 typedef vector<int>::iterator ITER;
12 
13 class Solution {
14 public:
15     TreeNode *buildTree_helper(ITER p_start, ITER p_end,
16                                ITER in_start, ITER in_end){
17         if(p_end == p_start)
18             return NULL;
19         if(in_start == in_end)
20             return NULL;
21         TreeNode *root = new TreeNode(*p_start);
22         ITER root_iter = find(in_start, in_end, root->val);
23         int lTreeSize = root_iter-in_start;
24         root->left = buildTree_helper(p_start+1,p_start+lTreeSize+1,in_start,root_iter);
25         root->right = buildTree_helper(p_start+lTreeSize+1,p_end,root_iter+1,in_end);
26         return root;
27     }
28 
29     TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
30         int n = preorder.size();
31         if(n==0)
32             return NULL;
33         return buildTree_helper(preorder.begin(),preorder.end(),inorder.begin(),inorder.end());
34     }
35 };