• 我的思路

• 递归法

  • 如果是二叉搜索树
  • 如果不是二叉搜索树

• 迭代法

• 我的思路

class Solution {
private:
    unordered_map<int, int> map;
    vector<int> result;
    void traversal(root) {
        if (root == NULL)   return;
        traversal(root->left);
        //  把root->val归到map里
        traversal(root->right);
    }
public:
    vector<int> findMode(TreeNode* root) {
        if (root == NULL)   return 0;
        traversal(root);
        //  把map里的众数存入result里
        return result;
    }
};

• 递归法
• 如果是二叉搜索树 那么中序遍历得到的树节点元素值是有序的

/**
 * 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:
     int maxCount = 0;
     int count = 0;
     TreeNode* pre = NULL;
     vector<int> result;

     void searchBST(TreeNode* cur) {
         // 为空
         if (cur == NULL)   return;
         // 遍历左子树
         searchBST(cur->left);
         // 处理中间节点
         // 1. 统计频率
         if (pre == NULL) {
             count = 1;
         } else if (pre->val == cur->val) {
             count++;
         } else {
             count = 1;
         }
        // 2. 更新结点
        pre = cur;
        // 3. 更新最大频率值和相应结果数组
        if (count == maxCount) {
            result.push_back(cur->val);
        }
        if (count > maxCount) {
            maxCount = count;
            result.clear();
            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;
    }
};

• 递归法 如果不是二叉搜索树 需要借助map 需要sort函数结合自己写的cmp函数实现对map中的value排序

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;
    }
};

• 迭代法

中序遍历模板+前面递归法的中间处理逻辑

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        int maxCount = 0; // 最大频率
        int count = 0; // 统计频率
        vector<int> result;
        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) { // 如果和最大值相同，放进result中
                    result.push_back(cur->val);
                }

                if (count > maxCount) { // 如果计数大于最大值频率
                    maxCount = count;   // 更新最大频率
                    result.clear();     // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
                    result.push_back(cur->val);
                }
                pre = cur;
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};