文章
8
粉丝
42
获赞
14
访问
1.8k
(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...
登录后发布评论
暂无评论,来抢沙发