文章
7
粉丝
114
获赞
0
访问
551
评分及理由
(1)得分及理由(满分3分)
学生答案的基本设计思想:通过递归遍历二叉树,在遍历过程中计算左子树的最大值(Lmax)和右子树的最小值(Rmin),然后比较当前结点与Lmax和Rmin的差的绝对值是否相等,若相等则计数。该思想利用了二叉搜索树的性质(左子树的最大值即最右结点,右子树的最小值即最左结点),与标准答案的次优解思路一致。但答案中未明确说明如何获取Lmax和Rmin(例如通过递归返回子树极值),且递归函数参数flag的设计意图不清晰(用于区分左右子树处理),但整体思路正确。因此扣1分(语言描述不够清晰)。得2分。
(2)得分及理由(满分9分)
学生代码实现:
1. 使用递归后序遍历,尝试返回子树的极值(左子树返回最大值,右子树返回最小值),但代码逻辑存在多处错误:
- 递归函数参数flag(1表示左子树,2表示右子树)用于控制返回值,但返回值逻辑错误:当flag=1(左子树)时返回Rmin(右子树最小值),flag=2(右子树)时返回Lmax(左子树最大值),这不符合二叉搜索树的性质(左子树应返回最大值,右子树应返回最小值)。
- 对于非左右子树均存在的结点,返回值处理错误:例如只有左子树时返回Lmax(正确),但只有右子树时返回root->val(错误,应返回右子树的最小值,但这里直接返回当前值,未递归处理右子树的最小值)。
- 递归基线条件不完整:叶结点返回自身值正确,但空结点返回0(错误,应返回一个标识值,如-1,因为结点值均为正数)。
- 计数变量counts为全局变量,但函数原型应为`int countNodes(TreeNode* root)`,而学生答案多了参数flag,不符合题目要求。
2. 核心逻辑错误导致无法正确计算极值和比较最小距离,且函数接口与题目要求不一致。因此按严重逻辑错误扣分,仅得1分(思路正确但实现错误)。
(3)得分及理由(满分2分)
学生说明时间复杂度为O(n),但实际代码中递归遍历每个结点一次,且每个结点处理时间为常数(忽略递归调用),时间复杂度确为O(n)。但空间复杂度为O(1)错误(递归栈空间为O(h),h为树高)。由于时间复杂度正确,得1分。
题目总分:2+1+1=4分
登录后发布评论
暂无评论,来抢沙发