501. 二叉搜索树中的众数 递归法，拓展：普通二叉树求众数

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

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

假定 BST 满足如下定义：

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

示例 1：

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

提示：

• 树中节点的数目在范围 [1, 104] 内
• -105 <= Node.val <= 105

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

 法一：若为普通二叉树，并不是二叉搜索树的做法：采用unordered_map

/**
 * 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 {
private:
    
    bool static cmp(const pair<int,int>& a,const pair<int,int>& b){
        return a.second>b.second;
    }
    void inorder(TreeNode* root,unordered_map<int,int>& res){
        if(root){
            inorder(root->left,res);
            res[root->val]++;
            inorder(root->right,res);
        }
    }
public:
    vector<int> findMode(TreeNode* root) {
       vector<int> ans;
       if(!root) return ans;
       unordered_map<int,int> res;
       inorder(root,res);
       vectorint,int>> vec(res.begin(),res.end());
       sort(vec.begin(),vec.end(),cmp);
       ans.push_back(vec[0].first);
       for(int i=1;isize();i++){
           if(vec[i].second==vec[0].second){
               ans.push_back(vec[i].first);
           }
       }
       return ans;
    }
};

法二：利用二叉搜索树的特性，采用递归法

/**
 * 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 {
private:
   TreeNode* pre;
   int maxCount=INT_MIN;
   int count=0;
   void recursion(TreeNode* root,vector<int>& res){
       if(root){
           recursion(root->left,res);
            if(pre==NULL){
                count=1;
            }else if(pre->val==root->val){
                count++;
            }else{
                count=1;
            }
            if(maxCount==count){
                res.push_back(root->val);
            }
            else if(maxCount
                res.clear();
                res.push_back(root->val);
                maxCount=count;
            }
            pre=root;
           recursion(root->right,res);
           
       }
   }
public:
    vector<int> findMode(TreeNode* root) {
       vector<int> ans;
       recursion(root,ans);
       return ans;
    }
};

 参考代码：

代码随想录