---

题目描述

给你一个含重复值的二叉搜索树（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=1if (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){//如果当前数字数值出现次数最多就更新arrayListmaxCount=count;arrayList.clear();arrayList.add(root.val);} else if (count == maxCount) {//如果count等于maxCount，则再记录一个数值，因为众数可能不是一个arrayList.add(root.val);}pre=root;}middleSearch(root.right);}}