求二叉搜索树中的众数的三种方法

题目描述

法一：借助数组

将树中的元素中序遍历转移进数组中，依次遍历数组，计算每个元素出现的次数count，并及时更新最大数量maxCount，将对应的众数放入ans数组中。
该方法时间复杂度和空间复杂度均为O（n）

/**
 * Definition for a binary tree node.
 * 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 {
public:
    void midT(TreeNode* root, vector<int>& treeArr) {
        if (root == NULL) {
            return;
        }
        midT(root->left, treeArr);
        treeArr.push_back(root->val);
        midT(root->right, treeArr);
        return;
    }
    vector<int> findMode(TreeNode* root) {
        vector<int> treeArr;
        vector<int> ans;
        midT(root, treeArr);//将树中的元素转移到数组中
        int base=treeArr[0];//base是当前正在累加count的元素
        int count=0, maxCount=-1;
        treeArr.push_back(-1e5-1);//防止数组中最后一个元素检测不到
        int n=size(treeArr);

        for(int i=0; i<n; i++){
            if(base != treeArr[i]){//意味着base计数已经结束
                if(maxCount == count){//意味着base是当前遍历过的元素的众数之一
                    ans.push_back(base);
                }
                else if(maxCount < count){//意味着新的、数量更多的众数出现了
                    ans.clear();
                    ans.push_back(base);
                }

				//更新
                maxCount = max(maxCount, count);
                base = treeArr[i];
                count = 0;
            }
            count++;
        }
        return ans;

    }
};

法二：借助哈希表

将树中元素转移到哈希表，获取各元素出现的次数，再将哈希表转为vector二维数组并降序排序，其第一个元素就是众数之一，然后根据数量获取其他众数即可。该方法时间复杂度O（nlogn），空间复杂度O（n）

class Solution {
private:
    void searchBST(TreeNode* root, unordered_map<int,int>& map){
        if(root == NULL){
            return;
        }
        map[root->val]++;
        searchBST(root->left, map);
        searchBST(root->right, map);
        return;
    }
    bool static 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> ans;
        searchBST(root, map);//将树中元素转入哈希表
        vector<pair<int,int>> vec(map.begin(), map.end());//哈希表转换为二维数组
        sort(vec.begin(), vec.end(), cmp);
        ans.push_back(vec[0].first);//此时二维数组第一个元素一定是众数
        for(int i=1; i<vec.size(); i++){
            if(vec[i].second == vec[0].second){//找到其他众数
                ans.push_back(vec[i].first);
            }
            else break;
        }
        return ans;
    }
};

法三：直接在树上获取

这个方法用于完成进阶的要求，在中序遍历中直接完成，pre指向当前结点的前一个结点，便于比较是否相同，按照法一的逻辑进行更新。该方法时间复杂度和空间复杂度均为O（n），但是没有了额外的空间开销。

class Solution {
private:
    int count, maxCount;
    TreeNode* pre;
    vector<int> ans;

    void searchBST(TreeNode* root){//中序遍历
        if(root == NULL){
            return;
        }
        searchBST(root->left);//左

		//中
        if(pre == NULL){//第一个元素
            count = 1;
        }else if(root->val == pre->val){//同一个元素
            count++;
        }else{//下一个元素
            count = 1;
        }

		//更新最大值的逻辑同法一
        if(maxCount == count){
            ans.push_back(root->val);
        }else if(maxCount < count){
            maxCount = count;
            ans.clear();
            ans.push_back(root->val);
        }
        pre = root;

        searchBST(root->right);//右
        return;
    }
    
public:
    vector<int> findMode(TreeNode* root) {
        count = 0;
        maxCount = 0;
        pre = NULL;
        ans.clear();
        searchBST(root);
        return ans;
    }
};