力扣501 二叉搜索树中的众数

题目：

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
    结点左子树中所含节点的值 小于等于 当前节点的值
    结点右子树中所含节点的值 大于等于 当前节点的值
    左子树和右子树都是二叉搜索树

示例：

输入：root = [1,null,2,2]
输出：[2]

思路：

因为题目是二叉搜索树，所以依然可以用中序遍历，比较当前节点和上一节点的值，找到众数。

class Solution {
    //依然是采用左中右(中序)的顺序遍历，比较当前节点和上一节点的值
    TreeNode pre;//记录上一个遍历的节点
    ArrayList<Integer> resList;
    int maxCount;//记录最高频率值
    int count;
    public int[] findMode(TreeNode root) {
        resList = new ArrayList<>();
        maxCount = 0;
        count = 0;
        pre = null;
        findMode1(root);
        int[] res = new int[resList.size()];//list转数组
        for (int i = 0; i < resList.size(); i++) {
            res[i] = resList.get(i);
        }
        return res;
    }

    public void findMode1(TreeNode root){
        if(root==null){
            return;
        }
        //左
        findMode1(root.left);

        //中
        //计数
        if(pre==null||root.val!=pre.val) {
            count = 1;
        }else {//当前节点值等于上一节点值，出现次数+1
            count++;
        }
        //是否替换最高频率值
        if(count>maxCount){
            maxCount=count;//替换
            resList.clear();
            resList.add(root.val);
        }else if (count == maxCount) {
            resList.add(root.val);
        }
        pre = root;

        //右
        findMode1(root.right);
    }
}

 如果只是普通二叉树，则可以采用：

（1）遍历这棵树，用map统计频率（key放数，value放次数）

（2）把统计出来的出现频率（即map中的value）排个序

（3）取前面高频的元素

//java中按value对map排序
Map<String,String> map = new HashMap<>();
map.put("3","7");
map.put("2","5");
map.put("1","6");
List<Map.Entry<String,String>> list = new ArrayList<>(map.entrySet());
list.sort(Comparator.comparing(Map.Entry::getValue));
Map<String,String> map2 = new LinkedHashMap<>();
for(Map.Entry<String,String> entry: list){
    map2.put(entry.getKey(), entry.getValue());
}
map2.forEach((o1, o2)-> System.out.println(o1+":"+o2));

//按key对map排序
Map<String,String> map = new TreeMap<>(new Comparator<String>(){ 
    public int compare(String o1,String o2){ 
        return o2.compareTo(o1); //用正负表示大小值 
    } 
}); 
// lambda表达式写法 // 
Map<String,String> map1 = new TreeMap<>((o1,o2)->o2.compareTo(o1));