题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：
前序遍历先访问根节点然后再访问左右子树，中序遍历先访问左子树，然后访问根节点和右子树，因此前序遍历的第一个节点在中序遍历序列中，可以把中序序列分成两部分，左部分为该节点左子树，右部分为该节点右子树，利用递归思想，递归解决。
C++：
1.采用辅助函数
/*** 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) {int n1 = pre.size();int n2 = vin.size();if(n1 == 0 || n2 == 0 || n1 != n2)return NULL;TreeNode *root = Helper(pre, vin, 0, n1-1, 0, n2-1);return root;}TreeNode* Helper(vector<int> pre, vector<int> vin, int startPre, int endPre, int startVin, int endVin){if(startPre >= pre.size() || startVin >= vin.size()||startVin > endVin || startPre > endPre)return NULL;TreeNode *p = new TreeNode(pre[startPre]);int j = 0;//找到前序遍历第一个节点在中序序列中的位置while(vin[j] != pre[startPre] && j < vin.size()){++j;}//递归建立根节点左子树右子树p->left = Helper(pre, vin, startPre+1, j-startVin+startPre, startVin, j);p->right = Helper(pre, vin, j-startVin+startPre+1, endPre, j+1, endVin);return p;}
};
2.进一步优化，每次传入数组而不是边界位置
/*** 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) {int n1 = pre.size();int n2 = vin.size();if(n1 == 0 || n2 == 0 || n1 != n2)return NULL;vector<int> left_pre, left_in, right_pre, right_in;int j = 0;TreeNode *root = new TreeNode(pre[0]);while(vin[j] != pre[0]){++j;}for(int i = 0; i< j;++i){left_in.push_back(vin[i]);left_pre.push_back(pre[i+1]);//前序第一个为根节点}for(int i = j + 1; i < n1; ++i){right_in.push_back(vin[i]);right_pre.push_back(pre[i]);}root->left = reConstructBinaryTree(left_pre, left_in);root->right = reConstructBinaryTree(right_pre, right_in);return root;}
};