文章

20

粉丝

0

获赞

0

访问

2.4k

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

(1)算法基本设计思想

采用递归遍历的方式处理二叉搜索树的每个结点:

    对于当前结点,先判断是否同时存在左子树和右子树。

    若存在,分别找到左子树中与当前结点的最小距离(即左子树中最接近当前结点的值,因为二叉搜索树左子树所有值小于当前结点,所以左子树的最大值与当前结点的距离最小)和右子树中与当前结点的最小距离(右子树所有值大于当前结点,所以右子树的最小值与当前结点的距离最小)。

    比较这两个最小距离,若相等则计数加1。

     然后递归处理左子树和右子树,最终累加所有满足条件的结点数。

(2)算法实现(C++语言)
#include <iostream>
#include <cmath>
using namespace std;

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

// 辅助函数:找到左子树的最大值(左子树中与当前结点的最小距离对应值)
int findLeftMax(TreeNode* node) {
    while (node->right != NULL) {
        node = node->right;
    }
    return node->val;
}

// 辅助函数:找到右子树的最小值(右子树中与当前结点的最小距离对应值)
int findRightMin(TreeNode* node) {
    while (node->left != NULL) {
        node = node->left;
    }
&nbs...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发