【LeetCode】501. 二叉搜索树中的众数（Java）_leetcode 501 java

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

假定 BST 有如下定义：

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

解题思路

先遍历二叉树，把每个出现的数字，和数字的个数存放到map中，如果先遍历一次map的所有value，找出最大的出现次数max，和最大次数的相同个数count，创建count大的数组，再遍历map的所有key，如果map.get(key)等于最大值，则把key放到数组中，最后返回数组。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //记录每个出现的数字，和数字的个数
    private Map<Integer, Integer> map = new HashMap<>();

    public int[] findMode(TreeNode root) {
        //遍历二叉树填充map
        func(root);
        
        //找出数字最大的个数数
        int max = 0;
        //记录相同的值的个数，以便后面创建数组的个数
        int count = 0;
        for (Integer value : map.values()) {
            if (value > max) {
                max = value;
                count = 1;
            }
            else if (value == max)   count++;
        }
        int[] result = new int[count];
        
        //此时的count代表数组的存放下标
        count = 0;
        for (Integer key : map.keySet()) {
            if (map.get(key) == max)   result[count++] = key;
        }
        return result;
    }

    //递归遍历
    private void func(TreeNode tree) {
        //出口
        if (tree == null)   return;

        map.put(tree.val, map.containsKey(tree.val) ? map.get(tree.val) + 1 : 1);
        //遍历左子树
        func(tree.left);
        //遍历右子树
        func(tree.right);
    }
}
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

自己写的，没去看题解，效率不太好。