【20221103】【每日一题】二叉搜索树中的众数

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

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

假定 BST 满足如下定义：

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

---

思路：利用二叉搜索树的性质，还是使用中序遍历，双指针去遍历，一边记录相同的数出现的次数，一边更新Maxcount，同时实时的更新result数组。

class Solution {
public:
    TreeNode* pre=NULL;
    vector<int> result;
    int Maxcount=0,count=0;
    void traversal(TreeNode* cur){
        //左中右  中序遍历
        if(cur==NULL)   return;
        traversal(cur->left);//左
        //中
        if(pre==NULL)   count=1;
        else if(pre->val==cur->val) count++;
        else count=1;
        pre=cur;
        if(count==Maxcount)  result.push_back(cur->val);
        if(count>Maxcount){
            Maxcount=count;
            result.clear();
            result.push_back(cur->val);
        }  
        traversal(cur->right);//右
    }
    vector<int> findMode(TreeNode* root) {
        traversal(root);
        return result;
    }
};

---

另外一个就是当不为二叉搜索树，也就是树无序的时候，可以用map来做。把map转化为vector直接构造时用迭代器就行了。分为以下几个步骤：

1、遍历二叉树，把二叉树变为哈希表，其中key对应出现的值，value对应出现的频率；

2、把哈希表再转成数组，注意这里转成数组时，vector放的是pair对；

3、编写sort的排序规则，要加static，对数组进行排序；

4、取第一个元素的second，并遍历数组找到相同的，都压入result中。

---

暂时没有理解的是：在设置sort的排序规则的谓词时，要加上static，否则无法通过。

class Solution {
public:
    //遍历二叉树，把值都放进map中
    unordered_map<int,int> hash;
    void traversal(TreeNode* node){
        //因为无序，所以遍历顺序理论上也不重要
        if(node==NULL)  return;
        traversal(node->left);
        hash[node->val]++;//map的key值对应出现的值，value对应出现的频率
        traversal(node->right);
    }
    //排序规则，按照频率由高到低排列
    bool static comp(const pair<int,int>& a,const pair<int,int>& b){
        return a.second>b.second;
    }
    vector<int> findMode(TreeNode* root) {
        traversal(root);
        //map无法对value进行排序，所以还得把map变成vector
        vectorint,int>> vec(hash.begin(),hash.end());
        //sort (起始迭代器，终止迭代器，谓词)
        sort(vec.begin(),vec.end(),comp);
        vector<int> result;
        result.push_back(vec[0].first);
        for(int i=1;isize();i++)
        {
            if(vec[i].second==vec[0].second) 
                result.push_back(vec[i].first);
        }
        return result;
    }
};