文章

7

粉丝

0

获赞

0

访问

3.9k

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

(1)算法设计思想:遍历二叉搜索树(BST),对每个同时存在左、右子树的节点:

利用 BST 特性,左子树最大值是左子树最右节点(与当前节点距离最小),右子树最小值是右子树最左节点(与当前节点距离最小);

计算 “当前节点值 - 左子树最大值” 和 “右子树最小值 - 当前节点值”,若两距离相等则计数加 1;

递归或迭代遍历所有节点,最终返回计数结果。

(2)C 语言代码:

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 找BST左子树的最大值(最右节点)
int findLeftMax(TreeNode* root) {
    while (root->right != NULL) {
        root = root->right;
    }
    return root->val;
}

// 找BST右子树的最小值(最左节点)
int findRightMin(TreeNode* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root->val;
}

int countNodes(TreeNode* root) {
    if (root == NULL) return 0; // 空节点,计数0
    int count = 0;
    // 节点同时有左右子树
    if (root->left != NULL && root->right != NULL) {
        int leftMax = findLeftMax(root->left);
        int rightMin = findRightMin(root->right);
        // 判断两个最小距离是否相等
        if ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发