501. 二叉搜索树中的众数(一般)

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
例如：
给定 BST [1,null,2,2],

1

2
/
2
返回[2].

提示：如果众数超过1个，不需考虑输出顺序

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree

思路：

中序遍历产生的数组，众数都在一起，在中序遍历中处理这个逻辑

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    int crowd = 0;
    int maxCrowd = 0;
    TreeNode pre = null;
    //输出是个数组,还得List实现
    List<Integer> res = new ArrayList<>();
    public int[] findMode(TreeNode root) {
        //中序遍历，众数一定出现在相邻地方，还得计数，考虑出现频率
        inorder(root);
        int[] out = new int[res.size()];
        for(int i=0;i<res.size();i++){
            out[i] = res.get(i);
        }
        return out;

    }
    public void inorder(TreeNode root){
        if(root==null){
            return;
        }
        //左
        inorder(root.left);
        //计数，中
        if(pre==null){
            crowd=1;
        }else if(pre.val==root.val){
            crowd++;
        }else{
            crowd=1;
        }
        pre = root;
        //如果不止一个，这里考虑如果不是最大，如何处理
        if(crowd==maxCrowd){
            res.add(pre.val);
        }
        if(crowd>maxCrowd){
            res.clear();
            res.add(pre.val);
            maxCrowd = crowd;
        }
        //右
        inorder(root.right);
    }
}