题目：
题解一：
遍历二叉树，利用哈希表记录每个节点出现的次数，然后找出次数最高的节点，时间复杂度：O(N)。
public int[] findMode(TreeNode root) {
Map<Integer, Integer> numberToCountMap = new HashMap<>();
dfsForFindMode(root, numberToCountMap);
int maxCount = 0;
for (Map.Entry<Integer, Integer> entry : numberToCountMap.entrySet()) {
Integer count = entry.getValue();
if (count >= maxCount) {
maxCount = count;
}
}
List<Integer> modeList = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : numberToCountMap.entrySet()) {
Integer number = entry.getKey();
Integer count = entry.getValue();
if (count == maxCount) {
modeList.add(number);
}
}
return modeList.stream().mapToInt(Integer::intValue).toArray();
}
private void dfsForFindMode(TreeNode node, Map<Integer, Integer> numberToCountMap) {
if (node == null) {
return;
}
dfsForFindMode(node.left, numberToCountMap);
numberToCountMap.put(node.val, numberToCountMap.getOrDefault(node.val, 0) + 1);
dfsForFindMode(node.right, numberToCountMap);
}题解二：
二叉搜索树的中序遍历为有序序列，那么众数必然是连续的，我们在中序遍历时记录当前数字出现的次数，如果出现次数更高的数字则不断更新结果直至遍历结束，时间复杂度：O(N)。
private List<Integer> resultList = new ArrayList<>();
int maxCount = 0, base = 0, count = 0;
public int[] findMode(TreeNode root) {
dfsForFindMode(root);
return resultList.stream().mapToInt(Integer::intValue).toArray();
}
private void dfsForFindMode(TreeNode node) {
if (node == null) {
return;
}
dfsForFindMode(node.left);
update(node.val);
dfsForFindMode(node.right);
}
private void update(int number) {
// 当前number次数+1
if (number == base) {
count++;
} else {
// 遇到新的数字，更新base
base = number;
count = 1;
}
// 当前数字出现次数等于最大次数，添加众数
if (count == maxCount) {
resultList.add(number);
}
// 当前数字出现次数最高，属于唯一众数，需要更新maxCount，resultList
if (count > maxCount) {
resultList.clear();
maxCount = count;
resultList.add(number);
}
}
