501. 二叉搜索树中的众数

501. 二叉搜索树中的众数

#树 2024-11-13

class Solution {
public:
    void collectData(TreeNode* root){
        if(root == nullptr) return;
        data[root->val]++;
        collectData(root->left);
        collectData(root->right);
    }
    vector<int> findMode(TreeNode* root) {
        collectData(root);

        // 针对 value 进行排序
        for(const auto& item : data){
            sortData.push_back(make_pair(item.first,item.second));
        }
        sort(sortData.begin(),sortData.end(),[&](auto left,auto right){
            return left.second > right.second;
        });

        // 取出合理的结果
        result.push_back(sortData[0].first);
        for(int i = 1; i < sortData.size(); i++){
            if(sortData[0].second == sortData[i].second){
                result.push_back(sortData[i].first);
            }else{
                break;
            }
        }

        return result;
    }

private:
    unordered_map<int,int> data;
    vector<pair<int,int>> sortData;
    vector<int> result;
};

这里用到针对 map 或 unordered_map 容器的 value 进行排序，理论上只支持 key 的排序，即 map 本身是自动机械能 key 排序的。如果要进行 value 排序，就需要将其大包围 pair 放到 vector 中，然后利用 sort 的自定义排序函数的方式进行 value 的排序。

上面这个方式比较通用，但此题明确是二叉搜索树，能不能利用这个特性完成更高效的解题？

二叉搜索树中序遍历是有序的，那么我们就可以轻易统计了。

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.push_back(cur->val);
        }

        searchBST(cur->right);   
        return ;
    }

public:
    vector<int> findMode(TreeNode* root) {
        searchBST(root);
        return result;
    }
};