题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 二叉树节点的定义如下： struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) { if(pre.size() == 0){ //前序遍历为空，返回NULL return NULL; } TreeNode *root = new TreeNode(pre[0]); //前序的第一个元素是根结点 vector<int> left_pre,right_pre,left_in,right_in; //保存前序的左右子树和中序的左右子树 int i = 0; int j = 0; while(i < in.size()&& root->val != in[i]) { //查看中序中的元素是否等于pre[0]，用i标记其位置 i++; } for( j = 0;j < i;j++){ //找到根结点的位置 left_in.push_back(in[j]); left_pre.push_back(pre[j+1]); } for(j = i+ 1 ;j < in.size();j++){ right_pre.push_back(pre[j]); right_in.push_back(in[j]); } root->left = reConstructBinaryTree(left_pre,left_in); root->right = reConstructBinaryTree(right_pre,right_in); return root; }