文章

1

粉丝

0

获赞

0

访问

395

头像
2025 年 9 月第 1 次 408 月考试卷 - 第41题回答
数据结构
发布于2025年9月23日 12:14
阅读数 395

(1)如果节点包含左节点,遍历左子树,统计左子树中最右节点的值,不存在左子树就返回当前节点的值,遍历右子树返回子树中最左节点的值,不存在右子树就返回当前节点的值,将当前节点的最左孩子和最右孩子返回给父节点,父节点同时存在左孩子和右孩子并且左孩子的最右节点等于右孩子的最左节点就计数最后返回计数值

(2)int countNodes(TreeNode * root){

}

 

(3)时间复杂度O(n) 空间复杂度最差O(N)为递归时所


评分及理由

(1)得分及理由(满分3分)

得分:1分

理由:学生的设计思想描述较为混乱,但提到了关键点:

  • 提到了"遍历左子树,统计左子树中最右节点的值"和"遍历右子树返回子树中最左节点的值" - 这对应标准答案中的次优解思路
  • 提到了"父节点同时存在左孩子和右孩子"的条件判断
  • 但描述不够清晰准确,如"左孩子的最右节点等于右孩子的最左节点"表述有误,应该是计算距离差值相等
  • 没有明确说明遍历方式(先序、中序还是后序)

(2)得分及理由(满分9分)

得分:0分

理由:

  • 学生只给出了函数框架int countNodes(TreeNode * root){ },没有任何具体实现代码
  • 没有递归逻辑,没有节点判断,没有距离计算,没有计数机制
  • 完全不符合题目要求的"采用C或C++语言描述算法,关键之处给出注释"

(3)得分及理由(满分2分)

得分:1分

理由:

  • 正确给出了时间复杂度O(n)
  • 提到了空间复杂度O(N)并说明了是递归栈空间
  • 但分析过于简单,没有详细说明时间复杂度是如何得出的

题目总分:1+0+1=2分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发