问题描述
LeetCode 501. 二叉搜索树中的众数 (opens in a new tab)，难度简单。
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数 (opens in a new tab)（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1
输入：root = [1,null,2,2] 输出：[2]
示例 2
输入：root = [0] 输出：[0]
提示：
- 树中节点的数目在范围
[1, 104]内 -105 <= Node.val <= 105
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
题解
class Solution {
private HashMap<Integer, Integer> map = new HashMap<>();
private void dfs(TreeNode node) {
if (node == null) {
return;
}
if (map.containsKey(node.val)) {
map.put(node.val, map.get(node.val) + 1);
} else {
map.put(node.val, 1);
}
dfs(node.left);
dfs(node.right);
}
public int[] findMode(TreeNode root) {
dfs(root);
List<Map.Entry<Integer, Integer>> sortedEntries = map.entrySet()
.stream()
.sorted(Map.Entry.comparingByValue())
.collect(Collectors.toList());
List<Integer> result = new ArrayList<>();
int value = sortedEntries.get(sortedEntries.size() - 1).getValue();
for (int i = sortedEntries.size() - 1; i >= 0; --i) {
if (sortedEntries.get(i).getValue() == value) {
result.add(sortedEntries.get(i).getKey());
}
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
}