AlgoPressAppearance
0501-二叉搜索树中的众数
https://leetcode.cn/problems/find-mode-in-binary-search-tree
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。 如果树中有不止一个众数，可以按 任意顺序 返回。 假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1： 
输入：root = [1,null,2,2]
输出：[2]
示例 2：
输入：root = [0]
输出：[0]
提示：
- 树中节点的数目在范围 [1, 10^4] 内
- -10^5 <= Node.val <= 10^5
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
思路：哈希表
遍历统计个数，将最大个数缓存，最后输出 Hash 表中的值为最大个数的值 问题：没有用到二叉搜索树的特性。
参考代码
csharp
public class Solution{
Dictionary<int,int> dict = new Dictionary<int,int>();
int max = 0;
private void dfs(TreeNode root){
if(root == null){
return;
}
dfs(root.left);
if(!dict.ContainsKey(root.val)){
dict.Add(root.val,1);
}
else{
dict[root.val]++;
}
max = Math.Max(dict[root.val],max);
dfs(root.right);
}
public int[] FindMode(TreeNode root) {
List<int> list = new List<int>();
dfs(root);
foreach(int key in dict.Keys){
if(dict[key] == max){
list.Add(key);
}
}
return list.ToArray();
}
}
思路2:中序遍历
二叉搜索树中序遍历，计算和 pre 的值是否相等，是的话累计结果输出
难点：如果没有重复的，需要输出所有数值，如果知道众数的最大个数(清空之前的收集)
参考代码
csharp
public class Solution {
List<int> result;
int pre = int.MinValue;
int preMax = 1;
int max = 1;
private void dfs(TreeNode root){
if(root == null){
return;
}
dfs(root.left);
if(pre == int.MinValue){
pre = root.val;
}
else{
if(pre == root.val){
max++;
//如果当前计数大于前面的总最大值，则清空结果
if(max > preMax){
result.Clear();
preMax = max;
}
}
else{
max = 1;
}
pre = root.val;
}
if(max == preMax){
if(!result.Contains(root.val)){
result.Add(root.val);
}
}
dfs(root.right);
}
public int[] FindMode(TreeNode root) {
result = new List<int>();
dfs(root);
return result.ToArray();
}
}