文章

15

粉丝

0

获赞

1

访问

2.7k

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

1.利用中序遍历的思想,定义全局变量count,建立一个数组,分别记录各个结点的前驱和后继,统计两者与本结点的最小距离,若相等则将count加一,继续遍历直到完成,返回count

2.

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;
int counts = 0;
void MTraverse(TreeNode *T,int M[],int i){
    if(T==NULL){return ;}
    else {
        MTraverse(T->left,M,i-1);
        M[i] = T->val;
        //遍历数组找到比i小的元素中最大的值
        int max = 0;
        for (int j = 0; j < i; ++j) {
            if(M[j]>max){
                max = M[j];
            }
        }
        //找到比i大的元素中最大值
        int min = 0x7FFFFFFF;//C语言中的最大值
        for (int j = i+1; j < n; ++j) {
            if(M[j]<min){
                min = M[j];
            }
        }
        if(M[i]-max==min-M[i] && T->right!=NULL&&T->left!=NULL){
            counts++;
        }
        MTraverse(T->right,M,i+1);
    }
}
3.时间复杂度O(nlogn),空间复杂度O(n)

int funcs(TreeNode *T){
    //统计T中count的个数
   ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发