leetcode - 501 二叉搜索树中的众数 -java版_二叉搜索树的众数 java 递归

题目

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

假定 BST 有如下定义：

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

1

2
/
2
返回[2].

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

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

代码

/*
 * @lc app=leetcode.cn id=501 lang=java
 *
 * [501] 二叉搜索树中的众数
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private int max= 0;
    private List<Integer> res = new ArrayList<>();
    public int[] findMode(TreeNode root) {

        midt(root);
        return res.stream().mapToInt(Integer::valueOf).toArray();

    }

    private int pre =0;
    private int now =0;
    private void midt(TreeNode root  ) {
        if(root==null) return;
        midt(root.left);
        if(now==0){
            now++;
            pre = root.val;

        }else{
            if(pre == root.val){
                now++;

            }else{
                pre = root.val;
                now=1;
            }
        }
        if(now > max){
            res.clear();
            res.add(pre);
            max = now;
        }else if(max ==now){
            res.add(pre);
        }
        midt(root.right);
    }

    
}
// @lc code=end


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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60