【Leetcode笔记】501.二叉搜索树中的众数

题目要求

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

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

假定 BST 满足如下定义：

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

虽然题目对于BST的定义已经违背常识 ￣へ￣，但依据题意扩展解题思路是有意义的。
其次就是只要求出现频次最高的至少一个元素。

ACM 模式代码

#include <iostream>
#include <vector>
using namespace std;
#include <unordered_map>
#include <algorithm>

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) {}
};

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);
    }

    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;
        vector<int> result;
        if(root == NULL) return result;
        searchBST(root, map);
        vector<pair<int, int>> vec(map.begin(), map.end());
        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;
    }
};

int main(void)
{
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(2);
    Solution solution;

    vector<int> res = solution.findMode(root);
    for(int i = 0; i < res.size(); i++)
    {
        cout << res[i] << endl;
    }

    return 0;   
}

知识点

1. cmp函数必须声明为静态成员函数
   这是因为 sort() 函数为 STL 中的一个全局算法，并不依赖于任何类的特定实例；而sort想调用cmp函数就必须要保证cmp函数也是一个静态成员函数。
   也就是说，我们想使用Solution类里的findMode（）函数，就必须通过这样的方式：

    Solution solution;

    vector<int> res = solution.findMode(root);

而全局范围定义的函数就可以不用创建类的实例而直接调用，sort(vec.begin(), vec.end(), cmp);.
2. cmp 函数的输入参数需要 const 修饰

    static bool cmp(const pair<int, int>& a, const pair<int, int>& b)
    {
        return a.second > b.second; // 降序排列
    }

首先，传入的是 a 和 b 的引用，这样可以提高效率，避免复制操作产生临时变量；另外，因为在排序过程中，sort函数会频繁地访问这些参数，通过将参数声明为const，可以保证这些参数在函数执行过程中不会被修改，增强安全性和可读性。