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

题目描述

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

示例 1：

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

输入：root = [0]
输出：[0]

提示：

树中节点的数目在范围 [1, 104] 内
-105 <= Node.val <= 105

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

代码

使用非递归的方法

class Solution {
    public int[] findMode(TreeNode root) {
        //用map来存储节点的值和对应出现的次数
        HashMap<Integer,Integer> map = new HashMap<>();
        //使用非递归的方式中序遍历这棵二叉搜索树
        Stack<TreeNode> stack = new Stack<>();
        if (root==null){
            int[] res= new int[0];
            return res;
        }
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
            if (cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                //如果之前没记录过这个数就新增一个记录
                if(map.get(cur.val)==null){
                    map.put(cur.val, 1);
                }else {
                	//如果之前记录过就给次数加一
                    map.put(cur.val, map.get(cur.val)+1);
                }
                cur = cur.right;
            }
        }
        //找出出现次数最多的值
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        int maxCount = (int) Collections.max(map.values());


        List<Integer> list = new ArrayList<>();
        for (Map.Entry<Integer,Integer> entry:entries) {
            if (entry.getValue()==maxCount){
                list.add(entry.getKey());
            }
        }
        int []res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

}

使用递归的方法并且遍历的同时统计众数

class Solution {
    //对于二叉搜索树来讲，中序遍历就是从小到大的顺序
    int maxCount=0;
    int count=0;
    ArrayList<Integer> arrayList = new ArrayList<>();//临时存储结果，动态地增加结果
    TreeNode pre=null;//用来表示当前节点的上一个节点
    public int[] findMode(TreeNode root) {
        middleSearch(root);
        int[] res = new int[arrayList.size()];
        for (int i = 0; i < arrayList.size(); i++) {
            res[i] = arrayList.get(i);
        }
        return res;
    }
    //使用递归的方法中序遍历
    public void middleSearch(TreeNode root){
        //递归出口
        if (root==null){
            return;
        }
        middleSearch(root.left);
        //处理中间节点
        //如果这是第一个节点或者之前节点的值与当前节点的值不相等就让count=1
        if (pre==null||pre.val!= root.val){
            count=1;
            if (pre==null){
                arrayList.add(root.val);
                maxCount=count;
            } else if (count == maxCount) {
                //如果count等于maxCount，则再记录一个数值，因为众数可能不是一个
                arrayList.add(root.val);
            }
            pre=root;
        }else {
            count++;
            if (count>maxCount){//如果当前数字数值出现次数最多就更新arrayList
                maxCount=count;
                arrayList.clear();
                arrayList.add(root.val);
            } else if (count == maxCount) {
                //如果count等于maxCount，则再记录一个数值，因为众数可能不是一个
                arrayList.add(root.val);
            }
            pre=root;
        }
        middleSearch(root.right);
    }

}