文章
4
粉丝
0
获赞
0
访问
286
评分及理由
(1)得分及理由(满分3分)
学生答案中描述了基本思路:对每个结点判断是否存在左右子树,若存在则计算左子树最大值与当前结点的差的绝对值(即左子树最小距离),以及右子树最小值与当前结点的差的绝对值(即右子树最小距离),并比较是否相等。该思路利用了二叉搜索树的性质(左子树最大值即最右结点,右子树最小值即最左结点),与标准答案中的“次优解”设计思想一致。但描述中未明确说明如何获取左子树最大值和右子树最小值(例如通过循环查找最右/最左结点),且部分细节(如遍历方式)未提及。因此扣1分,得2分。
(2)得分及理由(满分9分)
学生提供的代码存在以下问题:
1. 函数原型错误:题目要求函数原型为`int countNodes(TreeNode* root)`,但学生代码中为`int countNodes(TreeNode *p, int count)`,多了一个参数`count`,且未正确初始化(函数内将`count`置0会导致递归调用时丢失计数)。
2. 逻辑错误:在判断左右子树存在后,直接取左孩子和右孩子的值(`m1 = p->left->data`和`m2 = p->right->data`),这仅获取了直接子结点的值,而非左子树的最大值或右子树的最小值,不符合二叉搜索树的性质(左子树的最大值应为最右结点,右子树的最小值应为最左结点)。
3. 函数调用错误:使用`return comp1(...)`和`return comp2(...)`会导致函数提前返回,无法继续执行后续比较和递归。
4. 未实现递归遍历:代码中没有递归调用`countNodes`遍历左右子树,无法统计所有结点。
5. 辅助函数`comp1`未正确定义(无参数列表和返回值),且未实际用于计算绝对值。
基于以上严重逻辑错误和代码结构问题,该部分得分0分。
(3)得分及理由(满分2分)
学生答案中写了时间复杂度为O(n),但根据其代码实现(未正确实现遍历和查找),实际时间复杂度无法达到O(n)。且其思路对应的“次优解”标准时间复杂度应为O(nh)(h为树高),因此判断错误,得0分。
题目总分:2+0+0=2分
登录后发布评论
暂无评论,来抢沙发