题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：
递归调用，分左右块进行构建。
class Solution
{
public:
TreeNode *reConstructBinaryTree(vector<
int> pre, vector<
int>
vin)
{
return helper(pre,
0, pre.size() -
1, vin,
0, vin.size() -
1);
}
TreeNode *helper(vector<
int> pre,
int pbeg,
int pend, vector<
int> vin,
int vbeg,
int vend)
{
if (pbeg > pend || vbeg >
vend)
return NULL;
TreeNode *res =
new TreeNode(pre[pbeg]);
int index =
0;
while (index <
vend)
{
if (vin[index] ==
pre[pbeg])
break;
index++
;
}
cout << res->val <<
endl;
res->left = helper(pre, pbeg +
1, pend + index - vbeg, vin, vbeg, index -
1);
res->right = helper(pre, pbeg +
1 + index - vbeg, pend, vin, index +
1, vend);
return res;
}
};
转载于:https://www.cnblogs.com/ruoh3kou/p/10043102.html
相关资源：数据结构—成绩单生成器
