力扣第501题二叉树的众数 c++ (暴力加双指针优化）-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣第501题二叉树的众数 c++ (暴力加双指针优化）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

501. 二叉搜索树中的众数

简单

思路和解题方法一（暴力）

定义一个私有函数searchBST，用于前序遍历二叉搜索树，并统计每个元素的频率。函数参数包括当前节点指针cur和存储元素频率的unordered_mapmap。

在searchBST函数中，如果当前节点为空，则直接返回；否则，对当前节点的值进行统计，将当前节点的值作为map的键，并将对应的值加1，表示该元素出现的频率。

递归调用searchBST函数，传入当前节点的左子节点和map，再传入当前节点的右子节点和map，实现前序遍历。

定义一个静态成员函数cmp，用于比较两个pair类型的元素，按照频率降序排列。在排序时使用此比较函数。

在findMode函数中，首先创建一个空的unordered_map类型的map，用于存储元素及其频率。

如果输入的根节点为空，直接返回空的结果数组。

调用searchBST函数，传入根节点和map，统计二叉搜索树中每个元素的频率。

将map转化为vector类型，并使用sort函数对vector进行排序，排序方式为按照元素的频率降序排列。

创建一个空的结果数组result，将排序后的第一个元素的键（也就是出现频率最高的元素）添加到result中。

遍历排序后的vector，从第二个元素开始，如果其频率和第一个元素的频率相同，则将其键添加到result中；否则结束遍历。

返回结果数组result。

复杂度

时间复杂度:

O(n logn)

时间复杂度：

前序遍历二叉树的时间复杂度为 O(n)，其中 n 是二叉树的节点数。

构建哈希表的过程中，对每个节点进行插入操作的平均时间复杂度为 O(1)。因此构建哈希表的时间复杂度也是 O(n)。

对哈希表进行排序的时间复杂度为 O(nlogn)。

综上所述，算法的时间复杂度为 O(n) + O(n) + O(nlogn) = O(nlogn)。

空间复杂度

O(n)

空间复杂度：

使用了一个哈希表来存储元素及其频率，哈希表的空间复杂度是 O(n)。

将哈希表转换成了向量，空间复杂度仍然是 O(n)。

保存结果的向量，最多可能存储所有节点的值，因此空间复杂度也是 O(n)。

综上所述，算法的空间复杂度为 O(n)。

c++ 代码

class Solution {
private:
    // 前序遍历二叉搜索树，统计每个元素的频率
    void searchBST(TreeNode* cur, unordered_map<int, int>& map) {
        if (cur == NULL) return ;
        map[cur->val]++; // 统计元素频率
        searchBST(cur->left, map); // 遍历左子树
        searchBST(cur->right, map); // 遍历右子树
        return ;
    }
    // 静态成员函数，用于比较两个pair类型元素，按照频率降序排列
    static bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second;
    }
public:
    vector<int> findMode(TreeNode* root) {
        unordered_map<int, int> map; // 存储元素及其频率的map，key为元素，value为频率
        vector<int> result; // 结果数组
        if (root == NULL) return result; // 根节点为空，直接返回空结果数组
        searchBST(root, map); // 统计二叉搜索树中每个元素的频率
        vector<pair<int, int>> vec(map.begin(), map.end()); // 将map转换为vector
        sort(vec.begin(), vec.end(), cmp); // 按照频率降序排列
        result.push_back(vec[0].first); // 将频率最高的元素添加到结果数组中
        for (int i = 1; i < vec.size(); i++) {
            // 遍历排序后的vector，如果元素频率与第一个元素的频率相同，则添加到结果数组中；否则结束遍历
            if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
            else break;
        }
        return result; // 返回结果数组
    }
};

思路和解题方法二（双指针加时时优化）

使用了一个全局变量 maxCount 来记录最大频率，使用 count 来统计当前节点值出现的频率。同时，引入了一个 pre 变量来记录前一个访问的节点，以便比较当前节点与前一个节点的值是否相同。

函数 searchBST 是进行中序遍历的辅助函数，通过递归遍历左子树、处理当前节点、递归遍历右子树的顺序进行搜索。在处理当前节点时，首先判断当前节点值与前一个节点值是否相同，若相同则将 count 增加 1，否则将 count 重置为 1。然后，根据 count 的大小与 maxCount 进行比较，并更新 maxCount 和 result。如果 count 与 maxCount 相同，说明当前节点值出现的频率与最大频率相同，将其加入 result 中。如果 count 大于 maxCount，则更新 maxCount 并清空 result，将当前节点值放入 result 中。

在 findMode 函数中，初始化各个变量，然后调用 searchBST 开始搜索，并返回结果数组 result。

复杂度

时间复杂度:

O(n)

时间复杂度是O(n)，其中n是二叉搜索树中的节点数。因为我们需要遍历所有的节点来统计它们的频率。

空间复杂度

O(1)

不利用额外空间

c++ 代码

class Solution {
private:
    int maxCount = 0; // 最大频率
    int count = 0; // 统计频率
    TreeNode* pre = NULL; // 前一个节点
    vector<int> result; // 存储结果的向量

    // 中序遍历二叉搜索树，搜索出现频率最高的节点值
    void searchBST(TreeNode* cur) {
        if (cur == NULL) return; // 递归终止条件，当前节点为空

        searchBST(cur->left); // 左子树

        // 统计频率
        if (pre == NULL) { // 第一个节点
            count = 1;
        } else if (pre->val == cur->val) { // 与前一个节点数值相同
            count++;
        } else { // 与前一个节点数值不同
            count = 1;
        }
        pre = cur; // 更新上一个节点

        if (count == maxCount) { // 如果和最大频率相同，将节点值放进result中
            result.push_back(cur->val);
        }

        if (count > maxCount) { // 如果频率大于最大频率
            maxCount = count;   // 更新最大频率
            result.clear();     // 清空result，之前result中的元素都无效了
            result.push_back(cur->val);
        }

        searchBST(cur->right); // 右子树

        return ;
    }

public:
    vector<int> findMode(TreeNode* root) {
        count = 0;
        maxCount = 0;
        pre = NULL; // 初始化前一个节点为空
        result.clear(); // 清空result向量

        searchBST(root); // 调用中序遍历函数搜索出现频率最高的节点值

        return result; // 返回结果向量
    }
};

觉得有用的话可以点点赞，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦 >人< 。文章来源地址https://www.toymoban.com/news/detail-726594.html

到了这里，关于力扣第501题二叉树的众数 c++ (暴力加双指针优化）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！