501 二叉搜索树中的众数

本文最后更新于：2021年7月22日 晚上

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

假定 BST 有如下定义：

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

例如：
给定 BST [1,null,2,2],

1
2
3
4
5
1
 \
  2
 /
2

返回[2].

提示：如果众数超过1个，不需考虑输出顺序

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

Solution

参考 代码随想录

  • 递归法，适用于所有二叉树
  • 进行遍历，存入 map{num, freq} 中，然后再存入 map{freq, nums} 中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// @lc code=start
/**
 * 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> findMode(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) return res;
        traversal(root);
        map<int, vector<int>, greater<int>> map;
        for (auto iter = record.begin(); iter != record.end(); ++iter) {
            map[iter->second].push_back(iter->first);
        }
        res = map.begin()->second;
        return res;
    }
private:
    unordered_map<int, int> record;
    void traversal(TreeNode* root) {
        if (root == nullptr) return;
        traversal(root->left);
        record[root->val]++;
        traversal(root->right);
    }
};
// @lc code=end

  • 递归法，利用二叉搜索树中序有序的性质

  • 设置 pre 节点，频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集（以下代码为result数组）

「只需要遍历一遍二叉搜索树，就求出了众数的集合」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        res.clear();
        searchBST(root);
        return res;
    }
private:
    vector<int> res;
    int maxCount = 0;
    int cnt = 0;
    TreeNode* pre = nullptr;

    void searchBST(TreeNode* cur) {
        if (cur == nullptr) return;
        searchBST(cur->left);

        if (pre == nullptr) {
            cnt = 1;
        } else if (pre->val == cur->val) {
            cnt++;
        } else {
            cnt = 1;
        }
        pre = cur;
        if (cnt == maxCount) {
            res.push_back(cur->val);
        } else if (cnt > maxCount) {
            maxCount = cnt;
            res.clear();
            res.push_back(cur->val);
        }

        searchBST(cur->right);
        return;
    }
};
  • 迭代法，中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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()) {
            while (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } 
            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.push_back(cur->val);
            }
            pre = cur;
            cur = cur->right;               // 右
        }
        return result;
    }
};