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