Leetcode 501.二叉搜索树中的众数

力扣传送门

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

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

假定 BST 满足如下定义：

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

示例 1：

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

解题思路：

1. 给定一个二叉搜索树（BST），我们需要找到其中出现次数最多的元素（众数）。
2. 我们可以利用哈希表来进行统计。首先定义一个哈希表 hashmap，用于记录每个节点值出现的次数。
3. 接下来，使用深度优先搜索（DFS）对二叉树进行遍历。
4. 在 DFS 的过程中，对于每个节点，将其值加入到哈希表中，并更新对应节点值的出现次数。如果哈希表中已存在该节点值，则将其出现次数加1；否则，将其添加到哈希表中，并设置出现次数为1。
5. 在更新哈希表的过程中，同时记录出现次数的最大值 maxCount。
6. 完成 DFS 后，我们遍历哈希表，找到出现次数等于 maxCount 的节点值，将其加入到结果列表 modes 中。
7. 最后，将结果列表 modes 转换为数组，并返回结果数组。

总结起来，通过使用哈希表进行统计，我们可以在一次遍历二叉搜索树的过程中，实现对节点值出现次数的统计，并找到出现次数最多的节点值。这个方法的时间复杂度是 O(N)，其中 N 表示二叉树中的节点个数。

代码实现：

class Solution {
     // 存储众数的列表
    List<Integer> modes = new ArrayList();
    // 最大出现次数
    int maxCount; 
    // 哈希表用于统计节点值的出现次数
    HashMap<Integer, Integer> hashmap = new HashMap(); 

    public int[] findMode(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        // 进行深度优先搜索
        dfs(root); 

        // 遍历哈希表，找到出现次数等于最大次数的节点值
        for (Map.Entry<Integer, Integer> entry : hashmap.entrySet()) {
            int value = entry.getKey();
            int count = entry.getValue();

            if (count == maxCount) {
                modes.add(value);
            }
        }

        // 将结果列表转换为数组
        int[] result = new int[modes.size()];
        for (int i = 0; i < modes.size(); i++) {
            result[i] = modes.get(i);
        }
        return result;
    }

    // 深度优先搜索
    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        if (!hashmap.containsKey(root.val)) {
            hashmap.put(root.val, 1);
        } else {
            hashmap.put(root.val, hashmap.get(root.val) + 1);
        }
        maxCount = Math.max(maxCount, hashmap.get(root.val));
        dfs(root.left);
        dfs(root.right);
    }
}