501. 二叉搜索树中的众数
题目
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
提示： 如果众数超过1个，不需考虑输出顺序
进阶： 你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
解题思路
这题第一反应是直接遍历这个树，把元素出现的次数存入到一个HashMap中。但是这是一颗二叉搜索树，如果直接用HashMap效率太低了，可以考虑二叉搜索树的特性。
我们用中序遍历，比如一次中序遍历后的结果为{0,0,1,2,5,6,6}。我们可以发现，只要是一个数出现多次，那么它必是连续的。
①所以考虑用一个base，来存放当前元素，当下一次遍历的时候，我们只要拿即将遍历的元root.val和base比较
②如果相等，证明它们是同一个元素，这样的话count++；证明这个元素出现的次数加一。
③如果不等，那么更新base为root.val，并且重置count=1；这样就是一个新的元素，目前出现次数为1.
④经过上面两步后，我们再用一个MaxCount来存放之前遍历过的所有元素其中 出现次数最多的那个次数（有点绕口，简单来说就是存放的是到目前为止“出现最多的次数”注意！存放的是次数而不是元素）。
⑤那当前元素的出现次数count和maxCount比较。
⑥维护一个List 名叫answer，来存放出现次数最多的元素
⑦如果等于maxcount，证明它的出现次数和maxcount相等，即该元素出现次数也是最多的。就把root.val加入到answer中去。
⑧如果大于maxCount，那么证明出现了新的最大次数，我们更新maxcount=count；并且清空原来的answer数组，再把现在的root.val–也即是出现次数最多的那个元素存放到answer中。
⑨所有递归完成后，只要answer存放的就是答案了，但是题目要求int[]，我们再在主函数中把answer转成int[]就可以了
代码
class Solution {
List<Integer> answer = new ArrayList<Integer>();
int base, count, maxCount;//初始值都为0
/*
base：记录当前的数字
count： 记录当前数字重复的次数
maxCount： 维护已经扫描过的数当中出现最多的那个数字的出现次数
answer： 记录出现次数最多的元素（会经常更新）。
*/
public int[] findMode(TreeNode root) {
figureout(root);//这个方法执行完以后answer存放的就是出现次数最多的 哪些元素
int[] res=new int[answer.size()];
for(int i=0;i<answer.size();i++){
res[i]=answer.get(i);
}
return res;
}
public void figureout(TreeNode root){
if(root==null){
return ;
}
figureout(root.left);
if(root.val==base){//如果下一个元素和base相等则count+1
count++;
}else{//不相等就更新base，然后把count恢复为1
base=root.val;
count=1;
}
if(count==maxCount){//如果该元素的出现次数 和maxcount相等，就把该元素放入anser中
answer.add(root.val);
}else if(count>maxCount){//当前元素的出现次数大于MAXcount ，则count变成最大次数
maxCount= count;
answer.clear();//清空原来的集合，因为有更大的次数了，answer中只存放最大次数的元素，原来的已经不是最大的，所以要清空。
answer.add(root.val);//把新的“出现次数最多”的元素加入到anser中，以保证anser中总是存放的目前 “出现次数最多的” 数字
}
figureout(root.right);
}
}
