文章

156

粉丝

195

获赞

0

访问

28.5k

头像
2025 年 9 月第 1 次 408 月考试卷 - 第41题回答
数据结构
发布于2025年11月27日 17:47
阅读数 68

1)

基本设计思想:后序遍历二叉树,对于每个结点,若左右子树均存在,则左子树的最大值与当前结点值的差为左子树的最小距离,右子树的最小值与当前结点值的差为右子树的最小距离,若二者相等则计数。

2)

#include <limits.h>

// 返回: pair(子树最小值, 子树最大值)
// 同时通过引用参数 count 统计符合条件的结点数
void helper(TreeNode* root, int& count, int& minVal, int& maxVal) {
    if (!root) {
        minVal = INT_MAX;
        maxVal = INT_MIN;
        return;
    }
    
    int leftMin, leftMax;
    int rightMin, rightMax;
    
    helper(root->left, count, leftMin, leftMax);
    helper(root->right, count, rightMin, rightMax);
    
    // 更新当前子树的最小值和最大值
    minVal = (root->left) ? leftMin : root->val;
    maxVal = (root->right) ? rightMax : root->val;
    
    // 如果左右子树都存在
    if (root->left && root->right) {
        int leftDist = root->val - leftMax;  // 左子树最大值最接近当前结点值
        int rightDist = rightMin - root->val; // 右子树最小值最接近当前结点值
        if (leftDist == rightDist) {
            count++;
        }
    }
}

int countNo...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发