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