【LeetCode-501 | 二叉搜索树中的众数】

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <utility>
#include <algorithm>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

/* 一般方法:利用前序或中序或后序或层序遍历，对二叉搜索树进行遍历，统计每个节点出现的次数，因此使用到哈希表数据结构key代表节点，value代表节点出现的次数;接着将统计到的节点出现次数排序 */

class Solution
{
public:
    void Traversal(TreeNode *node, unordered_map<int, int> &map)
    {
        if (node == nullptr)
            return;
        map[node->val]++; // 根

        Traversal(node->left, map);  // 左
        Traversal(node->right, map); // 右
        return;
    }

    static bool cmp(pair<int, int> &a, pair<int, int> &b)
    {                               // pair数据结构中第一个元素是节点，第二个元素是节点出现的次数
        return a.second > b.second; // 降序
    }

    vector<int> findMode(TreeNode *root)
    {
        unordered_map<int, int> map;
        vector<int> result;
        if (root == nullptr)
            return result;

        Traversal(root, map);

        vector<pair<int, int>> vec(map.begin(), map.end()); // 将unordered_map转换成vector后再进行排序，转换时需要借助pair<int, int>数据结构
        sort(vec.begin(), vec.end(), cmp);                  // 按节点出现的次数，降序进行排列
        result.push_back(vec[0].first);

        for (int i = 1; i < vec.size(); i++)
        {
            if (vec[i].second == vec[0].second)
                result.push_back(vec[i].first);
            else
                break;
        }
        return result;
    }
};

/*
    特殊方法(只针对二叉搜索树):利用中序遍历，在遍历的过程中比较两个相邻节点(当前节点node和上一个节点pre)之间出现的次数大小
*/
class Solution
{
private:
    int count = 0;
    int maxCount = 0;
    TreeNode *pre = nullptr;
    vector<int> result;

public:
    void Traversal(TreeNode *node)
    {
        if (node == nullptr)
            return;
        Traversal(node->left);

        if (pre == nullptr) // 第1个节点出现
            count = 1;
        else if (pre->val == node->val) // 与前一个节点数值相同
            count++;
        else // 与前一个节点数值不同
            count = 1;

        pre = node;            // 更新上一个节点
        if (count == maxCount) // 如果和最大值相同，放进result中
            result.push_back(node->val);
        if (count > maxCount) // 因为众数不唯一，如果计数大于最大值频率
        {
            maxCount = count; // 更新最大值频率
            result.clear();   // 清除之前的统计结果result
            result.push_back(node->val);
        }

        Traversal(node->right);
        return;
    }

    vector<int> findMode(TreeNode *root)
    {
        result.clear();
        Traversal(root);
        return result; // 返回二叉搜索树中所有众数
    }
};