501. 二叉搜索树中的众数

Posted on | In
Words count in article: 356 | Reading time ≈ 1

题目

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

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

假定 BST 满足如下定义：

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

示例1：

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

示例2：

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

提示：

  • 树中节点的数目在范围 [1, 10^4] 内
  • -10^5 <= Node.val <= 10^5

进阶：

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

解法

解法一：

Java

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
int max = -1;
    public int[] findMode(TreeNode root) {
        if (Objects.isNull(root)) {
            return null;
        }
        Map<Integer, Integer> nums = new HashMap<>();
        travel(root, nums);
        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : nums.entrySet()) {
            if (entry.getValue() == max) {
                result.add(entry.getKey());
            }
        }
        int[] rr = new int[result.size()];
        for (int i = 0;i < result.size();i++) {
            rr[i] = result.get(i);
        }
        return rr;
    }

    private void travel(TreeNode root, Map<Integer, Integer> nums) {
        if (Objects.isNull(root)) {
            return;
        }

        travel(root.left, nums);
        int count  = nums.getOrDefault(root.val, 0) + 1;
        nums.put(root.val, count);
        if (max < count) {
            max = count;
        }
        travel(root.right, nums);
    }
0%