文章
78
粉丝
0
获赞
0
访问
36.5k
(1)从根节点开始递归查找路径,查找路径并每次用path记录当前路径,换路径时要注意删除之前的路径,最后打印答案
(2)
void find(BiNode* root,int pathLen,vector<int>&path,int sum,int k){
sum+=root->val;
if(sum==k){
for(int i=0;i<pathLen;i++){
cout<<path[i];//打印
}
}
}
if(root->lchild!=null){
path.push_back(root->lchild->val);
pathLen++;
find(root->lchild,pathLen,path,sum,k);//递归向左下查找
}
path.pop();//防止同时记录兄弟结点
pathLen--;//长度减一
if(root->rchild!=null){
path.push_back(root->rchild->val);
pathLen++;
find(root->lchild,pathLen,path,sum,k);//递归向右下查找
}
return ;
}
(3)时间复杂度是O(n),空间复杂度是O(1)
评分及理由
(1)得分及理由(满分4分)
学生答案仅提到“递归查找路径,记录路径,换路径时删除”,但未明确说明前序遍历顺序、回溯机制、路径和计算方式(特别是节点权值可能为负时仍需继续遍历的关键点)。设计思想描述过于简略,缺乏关键细节。扣2分。
得分:2分
(2)得分及理由(满分7分)
代码存在多处严重错误:
1. 函数原型与题目要求不符(参数列表错误,未使用BiTree和int* path,错误使用vector和额外sum参数)。
2. 递归入口未处理空节点(直接访问root->val会导致段错误)。
3. 路径记录逻辑错误:在递归左子树前push左孩子值(应记录当前节点值而非子节点值),导致路径顺序错误(根节点缺失)。
4. 递归右子树时错误调用左子树(find(root->lchild,...))。...
登录后发布评论
暂无评论,来抢沙发