原题：
Given preorder and inorder traversal of a tree, construct the binary tree.
题意很简单，根据一个先序遍历序列和一个中序遍历序列，生成二叉树。这道题记得考研的时候做过很多遍，一般都是以选择题的形式出现。我们将先从一个简单例子的开始，以手工的形式来解决这个问题，然后我们以该思路为基础，用编程将其实现。
给定如下两个序列：
preorder = [7, 5, 3, 6, 10, 8, 13]
inorder = [3, 5, 6, 7, 8, 10, 13]
我们来回忆一下先序遍历的过程，先从根节点出发，遍历左子树，左子树遍历完成后再遍历右子树。也就是说，preorder中第一个数字7即为整棵树根节点的值。再回忆下中序遍历的过程，先遍历左子树，完成后遍历根节点，最后遍历右子树。因此我们将preorder中的7在inorder中找出对应的位置，然后7的左边[3, 5, 6]即为左子树的所有节点，7的右边[8, 10, 13]即为右子树的所有节点。我们再来分析左子树，左子树总共有三个节点，它的中序遍历序列我们刚才已经得出，而先序遍历的过程是遍历完根节点后，再遍历左子树，因此7后面的三个数[5, 3, 6]即为左子树的先序遍历序列。然后我们再按照刚才对整棵树的分析分别对左子树右子树进行分析，如此反复，直到一棵树只剩一个节点为止。看到没有，我们再一次用到了“分而治之”的思想。
最后我们应该得到这样一幅图：
因此根据上述分析，我们设计出如下算法：
- 取先序列表的第一个值，创建根节点
- 寻找根节点的值在中序列表中的位置m，并计算左子树节点个数n
- 处理当前树的左子树，先序列表从下一个数开始，长度为n，中序列表还是第一个数开始，长度为n，回到过程1。
- 处理当前树的右子树，先序列表为去掉左子树后剩余的节点。中序列表为位置m的右半部分，回到过程1。
可能文字表述的不是很清楚，直接来看代码吧：
class Solution {
typedef vector<int>::iterator Pos;
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return constructTree(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
}
private:
/**
* 我们使用了一个help method来进行递归构建二叉树
* preBegin 先序列表的开始节点
* preEnd 先序列表的结束节点
* inBegin 中序列表的开始节点
* inEnd 中序列表的结束节点
*/
TreeNode* constructTree(Pos preBegin, Pos preEnd, Pos inBegin, Pos inEnd) {
TreeNode *node = NULL;
if (preEnd > preBegin && inEnd > inBegin) {
int val = *preBegin; //取先序列表第一个节点
node = new TreeNode(val);
Pos mid = find(inBegin, inEnd, val); //寻找在中序列表中的位置
int leftCount = mid - inBegin;
//对左子树跟右子树分别再进行处理
node->left = constructTree(preBegin + 1, preBegin + 1 + leftCount, inBegin, mid);
node->right = constructTree(preBegin + 1 + leftCount, preEnd, mid + 1, inEnd);
}
return node;
}
};
