文章

8

粉丝

42

获赞

14

访问

1.8k

头像
2025 年 9 月第 1 次 408 月考试卷 - 第41题回答
数据结构
发布于2025年9月25日 11:44
阅读数 118

(1)算法的基本设计思想

    1.    核心分析:对于满足“同时有左、右子树”的结点,其左子树中与该结点距离最小的结点是左子树的最大值结点(二叉搜索树左子树所有值小于根,最大值最接近根),右子树中距离最小的结点是右子树的最小值结点(右子树所有值大于根,最小值最接近根)。

    2.    计算逻辑:对每个符合条件的结点,计算“根值 - 左子树最大值”(左最小距离)和“右子树最小值 - 根值”(右最小距离),若两者相等则计数加1。

    3.    遍历方式:采用后序遍历(或任意遍历方式)遍历整棵树,对每个结点执行上述判断,最终返回计数结果。

(2)C语言算法实现
#include <limits.h>

// 函数:查找以root为根的子树中的最大值(用于左子树)
int findMax(TreeNode* root) {
    // 二叉搜索树最大值在最右结点
    while (root->right != NULL) {
        root = root->right;
    }
    return root->val;
}

// 函数:查找以root为根的子树中的最小值(用于右子树)
int findMin(TreeNode* root) {
    // 二叉搜索树最小值在最左结点
    while (root->left != NULL) {
        root = root->left;
    }
    return root->val;
}

// 递归遍历函数:统计满足条件的结点数
void traverse...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发