文章

24

粉丝

0

获赞

0

访问

2.1k

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

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

采用递归的方法遍历二叉搜索树。对于每个节点,首先判断是否同时存在左子树和右子树。如果存在,分别找到左子树中的最大值(因为二叉搜索树左子树所有节点值小于当前节点,所以左子树最大值是最右节点)和右子树中的最小值(右子树所有节点值大于当前节点,所以右子树最小值是最左节点)。计算当前节点与左子树最大值的距离,以及与右子树最小值的距离,若这两个距离相等,则该节点满足条件,计数加 1。然后递归处理左子树和右子树,统计满足条件的节点总数。

// 找到以node为根的子树中的最小值(最左节点)
int findMin(TreeNode *node) {
    while (node->left != NULL) {
        node = node->left;
    }
    return node->val;
}

int countNodes(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    int count = 0;
    // 判断是否同时存在左子树和右子树
    if (root->left != NULL && root->right != NULL) {
        // 左子树最大值与当前节点的距离
        int leftDist = abs(root->val - findMax(root->left));
        // 右子树最小值与当前节点的距离
        int rightDist = abs(root->val - findMin(root->right));
        if (leftDist == rightDist) {
            count++;
        }
    }
    // 递归统计左子树和右子树中满足条件的节点数
    count += countNodes(root->left);
    count += countNodes(root->right);
    return count...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发