题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
解题思路：
在二叉树的前序遍历序列中，第一个数字总是树的根节点的值。
在中序遍历序列中，根节点的值在序列的中间。根据前序遍历找到根节点后，中序遍历序列中，位于根节点左边的是左子树的结点的值，位于根节点右边的是右子树的结点的值。
如下图所示，前序遍历序列的第一个数字1就是根结点的值。扫描中序遍历序列，就能确定根结点的值的位置。根据中序遍历特点，在根结点的值1前面的3个数字都是左子树结点的值，位于1后面的数字都是右子树结点的值。
示例
同样，在前序遍历的序列中，根结点后面的3个数字就是3个左子树结点的值，再后面的所有数字都是右子树结点的值。这样我们就在前序遍历和中序遍历两个序列中，分别找到了左右子树对应的子序列。
既然我们已经分别找到了左、右子树的前序遍历序列和中序遍历序列，我们可以用同样的方法分别去构建左右子树。也就是说，接下来的事情可以用递归的方法去完成。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if( pre.empty() )
return NULL;
TreeNode* root = new TreeNode( pre[0] );
vector<int> left_pre, left_vin, right_pre, right_vin;
//left_vin
for( int i=0;vin[i]!=root->val;i++ )
left_vin.push_back(vin[i]);
//right_vin
for( int i=left_vin.size()+1;i<vin.size();i++)
right_vin.push_back(vin[i]);
//left_pre
for( int i=1;i<=left_vin.size();i++ )
left_pre.push_back(pre[i]);
//right_pre
for( int i=left_vin.size()+1;i<pre.size();i++ )
right_pre.push_back(pre[i]);
root->left = reConstructBinaryTree( left_pre, left_vin );
root->right = reConstructBinaryTree( right_pre, right_vin );
return root;
}
};
