LeetCode508-出现次数最多的子树元素和

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/most-frequent-subtree-sum/

中文链接：https://leetcode-cn.com/problems/most-frequent-subtree-sum/

题目详述

给出二叉树的根，找出出现次数最多的子树元素和。一个结点的子树元素和定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。然后求出出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的元素（不限顺序）。

示例 1
输入:

1
2
3
  5
 /  \
2   -3

返回 [2, -3, 4]，所有的值均只出现一次，以任意顺序返回所有值。

示例 2
输入:

1
2
3
  5
 /  \
2   -5

返回 [2]，只有 2 出现两次，-5 只出现 1 次。

提示： 假设任意子树元素和均可以用 32 位有符号整数表示。

题目详解

分为两步进行：

  • 计算所有子树元素和，以元素和为 key、出现次数为 value 存入哈希表中。
  • 遍历哈希表，找到出现次数最多的元素。
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
public class LeetCode_00508 {

    public int[] findFrequentTreeSum(TreeNode root) {
        Map<Integer, Integer> map = new HashMap<>();
        dfs(root, map);
        List<Integer> res = new ArrayList<>();
        int max = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int key = entry.getKey();
            int value = entry.getValue();
            if (value > max) {
                max = value;
                res.clear();
                res.add(key);
            } else if (value == max) {
                res.add(key);
            }
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }

    private int dfs(TreeNode root, Map<Integer, Integer> map) {
        if (root == null) {
            return 0;
        }
        int sum = root.val + dfs(root.left, map) + dfs(root.right, map);
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        return sum;
    }
}