文章

161

粉丝

0

获赞

0

访问

20.1k

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

(2)int countNodes(TreeNode* root) {

    if (root == NULL) return 0;

    int cnt = 0;

    if (check(root)) cnt = 1;

    return cnt + countNodes(root->left) + countNodes(root->right);

}

 

bool check(TreeNode* root) {

    if (root->left == NULL || root->right == NULL) 

        return false;

    return abs(root->left->val - root->val) == abs(root->right->val - root->val);

}

(3)时间复杂度:O(n)


评分及理由

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

学生未给出算法的基本设计思想,因此本部分得0分。

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

学生代码存在逻辑错误:在check函数中,仅比较了当前结点与直接左右子结点的差值,而题目要求的是左子树中所有结点与当前结点的最小距离和右子树中所有结点与当前结点的最小距离。学生代码未正确计算最小距离,因此不能正确统计满足条件的结点数。根据标准答案的评分标准,该代码逻辑错误严重,最多只能给予基本框架分。考虑到代码结构清晰且使用了递归遍历,但核心逻辑错误,扣分较多,得2分。

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

学生给出的时间复杂度为O(n),但实际由于check函数仅检查直接子结点,未遍历子树,所以时间复杂度确实是O(n)。然而,由于算法逻辑错误,时间复杂度分析虽正确但基于错误的前提。根据评分标准,时间复杂度分析正确可得满分,但考虑到算法本身错误,酌情扣1分,得1分。

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

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发