LeetCode 二叉搜索树中的众数（hash表）

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：

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

例如：

给定 BST [1,null,2,2],
   1
    \
     2
    /
   2
返回[2].

提示：如果众数超过1个，不需考虑输出顺序
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
思路分析： 最简单的思路就是使用hash表，将二叉搜索树中各个数字与其出现的次数进行关联。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxCnt = 0;//用于记录出现最多的次数
    unordered_map<int, int> numCntMap;//用于统计各个数字出现的次数
    vector<int> findMode(TreeNode* root) {
        vector<int> result;
        dfs(root);//中序遍历二叉树，统计各个数字出现的次数
        //然后找出所有出现次数为maxCnt的元素
        for (auto &item : numCntMap){
            if (item.second == maxCnt){
                result.push_back(item.first);
            }
        }
        return result;
    }
    //中序遍历二叉树，统计各个数字出现的次数
    void dfs(TreeNode* root){
        if (root == NULL){
            return;
        }
        dfs(root->left);
        maxCnt = max(maxCnt, ++numCntMap[root->val]);//更新出现次数最多的次数
        dfs(root->right);
    }
};

进阶： 充分利用二叉搜索树中序遍历为递增序列的特性，在中序遍历的同时进行众数的判定。（额外空间复杂度为O(1)）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> result;
    int maxCnt = 0;//用于记录出现最多的次数
    vector<int> findMode(TreeNode* root) {
        int lastNum = INT_MIN, cnt = 0;
        dfs(root, lastNum, cnt);
        return result;
    }
    //中序遍历二叉树，lastNum中序遍历前一个数字，cnt为前一个数字出现的次数
    void dfs(TreeNode* root, int &lastNum, int &cnt){
        if (root == NULL){
            return;
        }
        //第一步：遍历左子树
        dfs(root->left, lastNum, cnt);
        //第二步：访问根节点
        if (lastNum == root->val){
            //如果当前val与上一次的数字相等，计数器cnt自增
            cnt += 1;
        }
        else{
            //当前val与上一次的数字不相等，这在更新lastNum之前，需要对之前lastNum确认是不是当前的众数
            if (maxCnt < cnt){
                //lastNum出现次数cnt大于已经找到的出现次数的最大值，则之前找到的众数全部作废
                maxCnt = cnt;
                result.clear();
                result.push_back(lastNum);
            }
            else if (result.size() == 0 || (result.back() != lastNum && maxCnt == cnt)){
                //或者lastNum出现次数cnt等于已经找到的出现次数最大值，则lastNum也是众数中的一个
                result.push_back(lastNum);
            }
            //更新lastNum以及对应的cnt
            lastNum = root->val;
            cnt = 1;
        }
        //遍历右子树
        if (root->right != NULL){
            dfs(root->right, lastNum, cnt);
        }
        else{
            //如果右子树为空，则需要尝试进行新众数判定
            if (maxCnt < cnt){
                //lastNum出现次数cnt大于已经找到的出现次数的最大值，则之前找到的众数全部作废
                maxCnt = cnt;
                result.clear();
                result.push_back(lastNum);
            }
            else if (result.size() == 0 || (result.back() != lastNum && maxCnt == cnt)){
                //或者lastNum出现次数cnt等于已经找到的出现次数最大值，则lastNum也是众数中的一个
                result.push_back(lastNum);
            }
        }
    }
};