二叉搜索树的众数

首先我们可以先试一下如果他是个普通的二叉树，我们该如何处理这题，我们很容易想到用到map映射，键是搜索树结点的值，值是出现的频率。先把树遍历一遍，把map映射先初始化，然后对map的值进行排序，然后就很容易找到众数，但是unordered_map容器内部是无序的，也没有相关的函数使用，所以把map里的元素通过pair放到vector数组里面去，然后自己定义cmp函数，比较pair元素的second，也就是频率，把这个函数参数放到sort函数里面去，然后取与vector第一个元素频率相同的前几个就行

代码如下

class Solution {
private:

void searchBST(TreeNode* cur, unordered_map<int, int>& map) { // 前序遍历
    if (cur == NULL) return ;
    map[cur->val]++; // 统计元素频率
    searchBST(cur->left, map);
    searchBST(cur->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; // key:元素，value:出现频率
        vector<int> result;
        if (root == NULL) return result;
        searchBST(root, map);
        vector<pair<int, int>> vec(map.begin(), map.end());
        sort(vec.begin(), vec.end(), cmp); // 给频率排个序
        result.push_back(vec[0].first);
        for (int i = 1; i < vec.size(); i++) {
            // 取最高的放到result数组中
            if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
            else break;
        }
        return result;
    }
};

注意：
（1）在searchBST函数中定义map时，很容易忘掉其前面的&，因为这是遍历整个树，不需要返回值，所以这个map是改变的，所以要加&，不过记住以后函数参数用到map或者vector时都要要加&即可。
（2）然后就是对cmp的定义，可以记一下其规范的格式，同时pair不要忘记加&。

针对BST写法

class Solution {
private:
    int maxCount; // 最大频率
    int count; // 统计频率
    TreeNode* pre;
    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;
        TreeNode* pre = NULL; // 记录前一个节点
        result.clear();

        searchBST(root);
        return result;
    }
};

思路：
因为BST的特性，其中序遍历有序，所以我们就中序遍历它，然后需要一个前指针，方便遍历的时候与前一个元素的值进行比较，需要一个计数器，记录该结点的值出现次数，然后就是一个最大频率值，这个最大频率值是动态更新的，每当count大于它是就清空res的同时，把count赋值给它，然后再比较每当等于这个最大值就把值放进res。
这个是递归法，也可以用迭代的方法，利用一个栈进行操作,代码如下。

class Solution {
public:
    vector<int> findMode(TreeNode* cur) {
        vector<int> res;
        stack<TreeNode*> st;
        int count = 0;
        int maxCount = 0;
        TreeNode* pre = NULL;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) {
                st.push(cur);
                cur = cur->left;    //左
            } else {
                cur = st.top();   //中
                st.pop();
                if (pre == NULL) {
                    count = 1;
                } else if (pre->val == cur->val) {
                    count++;
                } else {
                    count = 1;
                }
                if (count == maxCount) {
                    res.push_back(cur->val);
                }
                if (count > maxCount) {
                    maxCount = count;
                    res.clear();
                    res.push_back(cur->val);
                }
                pre =cur;   //更新前指针
                cur = cur->right;   //右
            }
        }
        return res;
    }
};