Description

Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.

Examples 1
Input:

tree

return [2, -3, 4], since all the values happen only once, return all of them in any order.

Examples 2
Input:

tree

return [2], since 2 happens twice, however -5 only occur once.

Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.

Solution

DFS, time O(n), space O(n)

注意递归的时候sum和maxCount都要返回。因为我实在不喜欢static变量的写法啊，只能返回maxCount，以避免额外一次的遍历。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] findFrequentTreeSum(TreeNode root) {
        Map<Integer, Integer> sumToCount = new HashMap<>();
        int maxCount = findFrequentTreeSum(root, sumToCount)[1];
        
        List<Integer> res = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : sumToCount.entrySet()) {
            if (entry.getValue() == maxCount) {
                res.add(entry.getKey());
            }
        }
        
        return res.stream().mapToInt(i->i).toArray();
    }
    
    public int[] findFrequentTreeSum(TreeNode root, Map<Integer, Integer> map) {
        if (root == null) {
            return new int[]{0, 0};
        }
        
        int[] left = findFrequentTreeSum(root.left, map);
        int[] right = findFrequentTreeSum(root.right, map);
        int sum = left[0] + right[0] + root.val;
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        int maxCount = Math.max(map.get(sum), Math.max(left[1], right[1]));
        
        int[] res = new int[2];
        res[0] = sum;
        res[1] = maxCount;
        return res;
    }
}