文章

78

粉丝

0

获赞

0

访问

36.5k

头像
2025 年 7 月第 1 次 408 月考试卷 - 第41题回答
数据结构
发布于2025年9月19日 17:01
阅读数 422

(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,...))。...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发