2025 年 7 月第 1 次 408 月考试卷 - 第41题回答
（1）采用递归算法先序遍历二叉树，遍历时若当前节点不为空，每次将k加上当前节点的权值，并对pathLen加1。若节点为空，则循环输出path数组。
（2）
void FindValidpaths(BiTree T,int k,int *path,int pathLen){
if(T==NULL)
{
for(int i=0,i<pathLen;i++)
{
cout<<path[i];
}
}else
{
k=k+T.val;
pathLen++;
path[pathLen]=T.val;
FindValidpaths(T.left,k,path,pathLen);
FindValidpaths(T.right,k,path,pathLen);
}
}
(3)时间复杂度O（n2），空间复杂度O（n2）
评分及理由
（1）得分及理由（满分4分）
得分：1分
理由：
- 学生提到了递归先序遍历，这是正确的思路（+1分）
- 但是设计思想存在严重问题：题目要求路径权值和等于k，而学生描述的是"将k加上当前节点的权值"，这改变了k的含义，k应该是目标值而非累加变量
- 没有提到路径校验的关键步骤，也没有说明回溯操作
- 描述过于简略，没有完整阐述算法思想
（2）得分及理由（满分7分）
得分：2分
理由：
- 代码框架基本正确，使用了递归遍历（+1分）
- 有路径记录的基本思想（+1分）
- 但存在多个严重逻辑错误：
- 错误1：使用"k=k+T.val"改变了参数k的值，这会导致后续计算错误（-2分）
- 错误2：路径存储顺序错误，先pathLen++再存储，导致第一个节点存储在path[1]而非path[0]（-1分）
- 错误3：缺少回溯操作，没有在递归返回时减少pathLen（-1分）
- 错误4：缺少路径和校验的关键步骤，没有判断当前路径和是否等于k（-2分）
- 错误5：语法错误，使用C++的cout而非C语言的printf，且节点访问语法错误（T.val应为T->val）（-1分）
（3）得分及理由（满分2分）
得分：0分
理由：
- 时间复杂度O(n²)基本正确但缺乏分析过程
- 空间复杂度O(n²)完...
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发