输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例：
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]返回宽度优先搜索形式的二叉树，如下：
3 / \ 9 20 / \ 15 7 输出： [3,9,20,null,null,15,7]结合二叉树前序（根–左--右）与中序遍历（左–根--右）的规律来看，前序遍历的第一个数值一定是根节点的数值；根节点一定在中序遍历的中间，且左右两串数值分别是左右子树的节点。
根据这两个规律，我们来看示例：
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]preorder第一个数值 3 是根节点root的数值，在inorder中查询root所在的位置，3 的左边就是左子树的节点，3 的右边就是右子树的节点。根据inorder与root节点在其中的位置，我们可以知道当前根节点下左右子树分别具有多少节点。根据各自的节点数，我们在已有的preorder与inorder中可以提取左右子树的前序、中序遍历。
区分好根节点的左右子树以后，就是提取左右子树的前序遍历与中序遍历，这一步是为了达到遍历的初始条件：要想使用递归，就要提供与初始条件（这里是preorder与inorder）相同形式的条件。
不断地找到根节点、划分左右子树，递归到最后就能找到左右子树只有一个节点的情况。
class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if(preorder.empty()) // 没有子节点，返回空指针 return nullptr; if(preorder.size() == 1) // 只有一个子节点，返回该节点 { TreeNode *root = new TreeNode(preorder[0]); return root; } TreeNode *root = new TreeNode(preorder[0]); // 前序遍历第一个节点为根节点 // 在中序遍历中扫描根节点，根节点左右就是左右子树 auto itr = inorder.begin(); while (*itr != preorder[0]) ++itr; // 构造左子树前序中序 int left = itr - inorder.begin(); // 左子树节点数 vector<int> leftpre(preorder.begin()+1, preorder.begin()+1+left); vector<int> leftin(inorder.begin(), itr); // 构造右子树前序中序 vector<int> rightpre(preorder.begin()+1+left, preorder.end()); vector<int> rightin(++itr, inorder.end()); // 递归调用 root->left = buildTree(leftpre, leftin); root->right = buildTree(rightpre, rightin); // 返回根节点 return root; } };注释很详细了，这里最后返回根节点是不好想的，因为这里就是递归的思想所在，套娃套着套着就把自己套进去了，可以手写一个具体的二叉树画一画，看一看具体流程。
参考：
C++重建二叉树（带详细注释）
