LeetCode 501 ：二叉搜索树中的众数

小半 • 2023年2月3日上午10:53 • 技术随笔 • 阅读 186

题目：

思路：

众数即出现次数最多的数，
需要知道每个数出现的次数，
使用中序遍历，使节点按升序排列，同时统计每个数出现的次数
使用pre指针和root比较来辅助记数
使用list来记录出现次数最多的数
当确定count后，就可以确定root是否添加到list

用count来记录节点值重复的次数
①先确定count值才能确定是否添加root值
若pre为null，或者pre和root值不等时则开始记数；如果pre和root等则count++累加
②用count和max比较，如果count比max大，则之前list存的都无效，清除list
若count=max，即有新的众数出现，添加至list
若count<max，忽略

class Solution {
    int count=0;
    int max=Integer.MIN_VALUE;
    TreeNode pre=null;
    ArrayList<Integer> list;
    public int[] findMode(TreeNode root) {
        list=new ArrayList<>();
        check(root);
        int n=list.size();
        int[]r =new int[n];
        for(int i=0;i<n;i++){
            r[i]=list.get(i);
        }
        return r;

    }

    void check(TreeNode root){
        if(root==null){
            return;
        }
        check(root.left);
      //中序遍历
      //先记数
        if(pre==null || pre.val!=root.val){ // pre==null 写前面！防止空指针异常！
            count=1;
        }else if(root.val==pre.val){
            count++;
        }

    //再存入结果
        if(count>max){  // 若有重复的则只存count最高那个节点的值！
            list.clear();
            list.add(root.val);
            max=count;
        }else if(count==max){
            list.add(root.val);
        }
        //count<max则不存
        pre=root;
        check(root.right);
    }


}