501. 二叉搜索树中的众数 (opens new window)

1.中序遍历+记忆化搜索

性质：二叉搜索树的中序遍历是递增有序序列。

使用全局变量来保存当前节点值以及出现次数：

• 更新计数：
  • 如果是当前节点，则次数累加
  • 否则更新最大次数值，当前次数重置为1
• 结果统计：
  • 如果等于最大次数，那么当前节点值放入队列当中
  • 如果大于节点值，那么清空队列，然后将当前节点值加入队列。此处加了size判断条件防止同一个root被反复添加：
    • size==0：初始化刚加入第一个数的情况
    • size>2：当前当前次数第一次超过最大次数的情况(等于时root已经加入了一次)

class Solution {
    List<Integer> res=new ArrayList<>();
    int maxcount=Integer.MIN_VALUE;
    int currcount=1,preval=-100001;
    public int[] findMode(TreeNode root) {
        dfs(root);
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }
    public void dfs(TreeNode root){
        if(root.left!=null) dfs(root.left);
        //统计次数
        if(preval==root.val)currcount++;
        else{
            maxcount=Math.max(maxcount,currcount);
            preval=root.val;
            currcount=1;
        }
        //加入结果
        if(currcount==maxcount) res.add(root.val);
        if(currcount>maxcount&&res.size()!=1){
            res.clear();
            res.add(root.val);
        }
        if(root.right!=null) dfs(root.right);
    }
}