508. Most Frequent Subtree Sum 

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
class Solution {
    public int[] findFrequentTreeSum(TreeNode root) {
        Map<Integer, Integer> sumToCountMap = new HashMap<>();
        dfs(sumToCountMap, root);

        List<Integer> sumList = new ArrayList<>();
        int maxCount = 0;
        for (Map.Entry<Integer, Integer> entry : sumToCountMap.entrySet()) {
            int sum = entry.getKey(), count = entry.getValue();
            if (count > maxCount) {
                maxCount = count;
                sumList.clear();
                sumList.add(sum);
            } else if (count == maxCount) {
                sumList.add(sum);
            }
        }

        int[] res = new int[sumList.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = sumList.get(i);
        }
        return res;
    }

    private int dfs(Map<Integer, Integer> sumToCountMap, TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left = dfs(sumToCountMap, node.left);
        int right = dfs(sumToCountMap, node.right);

        int sum = left + node.val + right;
        sumToCountMap.put(sum, sumToCountMap.getOrDefault(sum, 0) + 1);
        return sum;
    }
}

References

508. Most Frequent Subtree Sum