题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回
思路：前序遍历的第一个为根节点，在中序遍历中查找根节点，划分左右子树，再递归求解
class Solution {
public:
int findMid(vector<
int> &vin,
int begin,
int end,
int number)
{
int idx;
for(idx=begin; idx<=end; ++
idx)
{
if(vin[idx]==number)
break;
}
return idx;
}
void reBuildTree(TreeNode **proot, vector<
int> &pre,
int preStart,
int preEnd, vector<
int> &vin,
int vinStart,
int vinEnd)
{
if(preStart>preEnd || vinStart>vinEnd)
return;
else{
(*proot)=
new TreeNode(pre[preStart]);
int mid=
findMid(vin, vinStart, vinEnd, pre[preStart]);//在中序数组中找到分界点
reBuildTree(&((*proot)->left), pre, preStart+
1, preStart+(mid-vinStart), vin, vinStart, mid-
1);//构建左子树
reBuildTree(&((*proot)->right), pre, preStart+(mid-vinStart)+
1, preEnd, vin, mid+
1, vinEnd);//构建右子树
}
}
TreeNode* reConstructBinaryTree(vector<
int> pre,vector<
int>
vin) {
TreeNode *root=
NULL;
reBuildTree(&root, pre,
0, pre.size()-
1, vin,
0, vin.size()-
1);//传入二级指针
return root;
}
};
1 class Solution {
2 public:
3 int getMid(vector<
int> &vin,
int begin,
int end,
int target)
4 {
5 while(vin[begin]!=target && begin<=end)++
begin;
6 return begin;
7 }
8 TreeNode * reBuildTree(vector<
int> &pre,
int &i, vector<
int> &vin,
int begin,
int end)
9 {
10 if(begin>end)
return NULL;
11 int mid=
getMid(vin, begin, end, pre[i]);
12 TreeNode * node=
new TreeNode(pre[i++
]);
13 node->left=reBuildTree(pre, i, vin, begin, mid-
1);
14 node->right=reBuildTree(pre, i, vin, mid+
1, end);
15 return node;
16 }
17 TreeNode* reConstructBinaryTree(vector<
int> pre,vector<
int>
vin)
18 {
19 if(pre.size()==
0 || vin.size()==
0 || pre.size()!=vin.size())
return NULL;
20 int i=
0;
21 return reBuildTree(pre, i, vin,
0, vin.size()-
1);
22 }
23 };
转载于:https://www.cnblogs.com/jeysin/p/8065318.html
相关资源：JAVA上百实例源码以及开源项目
