力扣 二叉搜索树中的众树

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

上代码

// 比较函数，用于qsort
int compare(const void * a, const void * b) {
    struct ValueCount *va = (struct ValueCount *)a;
    struct ValueCount *vb = (struct ValueCount *)b;

    return vb->count - va->count;
}

// 中序遍历二叉树，统计每个节点值的出现次数
void inorderTraversal(struct TreeNode *node, struct ValueCount **valueCounts, int *countIndex, int *maxSize) {
    if (node == NULL) {
        return;
    }

    inorderTraversal(node->left, valueCounts, countIndex, maxSize);

    int i;
    for (i = 0; i < *countIndex; i++) {
        if ((*valueCounts)[i].value == node->val) {
            (*valueCounts)[i].count++;
            break;
        }
    }
    if (i == *countIndex) {
        // 检查是否需要扩容数组
        if (*countIndex >= *maxSize) {
            // 扩容策略，这里简单地翻倍
            *maxSize *= 2;
            struct ValueCount *newArray = (struct ValueCount *)realloc(*valueCounts, sizeof(struct ValueCount) * (*maxSize));
            if (newArray == NULL) {
                // 处理内存分配失败的情况
                printf("内存分配失败！\n");
                exit(1);
            }
            *valueCounts = newArray;
        }
        (*valueCounts)[*countIndex].value = node->val;
        (*valueCounts)[*countIndex].count = 1;
        (*countIndex)++;
    }

    inorderTraversal(node->right, valueCounts, countIndex, maxSize);
}

// 找出众数并返回结果数组
int *findMode(struct TreeNode *root, int *returnSize) {
    // 初始分配足够的空间，这里假设初始大小为10
    int maxSize = 10;
    // 用于存储节点值及其出现次数的数组
    struct ValueCount *valueCounts = (struct ValueCount *)malloc(sizeof(struct ValueCount) * maxSize);
    int countIndex = 0;

    // 中序遍历二叉树，统计节点值出现次数
    inorderTraversal(root, &valueCounts, &countIndex, &maxSize);

    // 根据出现次数对valueCounts数组进行排序
    qsort(valueCounts, countIndex, sizeof(struct ValueCount), compare);

    // 找出最大出现次数
    int maxCount = valueCounts[0].count;

    // 统计众数的个数
    int modeCount = 0;
    for (int i = 0; i < countIndex; i++) {
        if (valueCounts[i].count == maxCount) {
            modeCount++;
        } else {
            break;
        }
    }

    // 分配返回结果数组的空间
    int *modes = (int *)malloc(sizeof(int) * modeCount);

    // 将众数填充到返回结果数组中
    int j = 0;
    for (int i = 0; i < countIndex && j < modeCount; i++) {
        if (valueCounts[i].count == maxCount) {
            modes[j] = valueCounts[i].value;
            j++;
        }
    }

    // 释放用于统计节点值出现次数的数组空间
    free(valueCounts);

    // 设置返回结果数组的大小
    *returnSize = modeCount;

    return modes;
}

思路很简单，思路就是先把树进行一个中序排序，接下来进行把一个一个数字都放到哈希表里面，然后一个一个循环哈希表里面的数字，进行排序。选出一个最大的来，思路就是这个样子