题目描述

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

假定 BST 有如下定义：

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

样例

给定 BST [1,null,2,2]，

   1
    \
     2
    /
   2

返回 [2]。

说明

• 如果众数超过 1 个，不需考虑输出顺序。

进阶

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

算法

(中序遍历) $O(n)$

1. 根据二叉搜索树的性质，可以采用中序遍历的方式遍历整棵树，这样就可以得到一个单调递增的序列，相同的元素会被一起遍历到。
2. 这样可以在遍历过程中统计众数。
3. 当然也可以使用哈希表直接统计出现次数最多的数字，详见代码 2。

时间复杂度

• 每个结点最多遍历一次，故时间复杂度为 $O(n)$。

空间复杂度

• 代码 1 除了记录答案的数组和递归使用的系统栈，其余只使用了常数内存空间。
• 代码 2 需要额外 $O(n)$ 的空间存储哈希表。

C++ 代码 1

/**
 * 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 {
public:
    void traverse(TreeNode *r, vector<int> &ans,
                 TreeNode* &pr, int &cur_count, int &max_count) {

        if (r == NULL)
            return;

        traverse(r->left, ans, pr, cur_count, max_count);

        if (pr == NULL || r->val == pr->val) {
            cur_count++;
        } else {
            if (cur_count > max_count) {
                max_count = cur_count;
                ans.clear();
            }

            if (cur_count == max_count)
                ans.push_back(pr->val);

            cur_count = 1;
        }

        pr = r;
        traverse(r->right, ans, pr, cur_count, max_count);
    }

    vector<int> findMode(TreeNode* root) {
        vector<int> ans;
        TreeNode *pr = NULL;
        int cur_count = 0, max_count = 0;

        traverse(root, ans, pr, cur_count, max_count);

        if (cur_count > max_count)
            return {pr->val};

        if (pr != NULL && cur_count == max_count)
            ans.push_back(pr->val);

        return ans;
    }
};

C++ 代码 2

/**
 * 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 {
public:
    void traverse(TreeNode *r, unordered_map<int, int> &v) {
        if (r == NULL)
            return;

        traverse(r->left, v);
        v[r->val]++;
        traverse(r->right, v);
    }

    vector<int> findMode(TreeNode* root) {
        if (!root)
            return {};

        unordered_map<int, int> v;
        traverse(root, v);

        int ma = v[root->val];
        for (const auto &it : v)
            ma = max(ma, it.second);

        vector<int> ans;
        for (const auto &it : v)
            if (it.second == ma)
                ans.push_back(it.first);

        return ans;
    }
};