二叉搜索树中的众数

题目：

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

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

假定 BST 满足如下定义：

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

思路1：

在先序遍历中使用unordered_map记录每个节点的值和出现的次数。遍历map，查找

class Solution {
public:
    void PreOrder(TreeNode* root, unordered_map<int, int>& map_num)
    {
        if(NULL == root) return;
        map_num[root->val]++;
        PreOrder(root->left, map_num);
        PreOrder(root->right, map_num);
    }
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        unordered_map<int, int> map_num;
        PreOrder(root, map_num);
        int max = map_num.begin()->second;
        for(auto iter=map_num.begin(); iter!=map_num.end(); ++iter)
        {
            if(iter->second > max) max = iter->second;
        }
        for(auto iter=map_num.begin(); iter!=map_num.end(); ++iter)
        {
            if(iter->second == max) res.emplace_back(iter->first);
        }
        return res;
    }
};

但是，上述的方法适合所有类型的二叉树，并没有利用二叉搜索树的性质

思路2：

使用中序遍历，这时相同的数值都会是邻近的，计算当前元素与前一个元素是否相同；若相同，则count+1;设置最大值max_count,若count>max_count,则把result的值清空，把max_count = count.

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，之前result里的元素都失效了
            result.push_back(cur->val);
        }

        searchBST(cur->right);      // 右
        return ;
    }

public:
    vector<int> findMode(TreeNode* root) {
        count = 0;
        maxCount = 0;
        pre = NULL; // 记录前一个节点
        result.clear();

        searchBST(root);
        return result;
    }
};

需要在递归中，注意pre变量。