[508. Most Frequent Subtree Sum] #leetcode

508_0904.java

class Solution {
  // O(n) O(n)
    public int[] findFrequentTreeSum(TreeNode root) {
        HashMap<Integer, Integer> sums = new HashMap<Integer, Integer>();
        
        dfs(root, sums);
        
        List<Integer> res = new ArrayList<Integer>();
        int max = 0;
        
        for(Map.Entry<Integer, Integer> entry : sums.entrySet()) {
            if (entry.getValue() > max) {
                res = new ArrayList<Integer>();
                res.add(entry.getKey());
                max = entry.getValue();
            } else if (entry.getValue() == max) {
                res.add(entry.getKey());
            }
        }
        
        return res.stream().mapToInt(i->i).toArray();
    }
    
    private Integer dfs(TreeNode node, HashMap<Integer, Integer> sums) {
        if (node == null) return 0;
        
        int sum = node.val;
        sum += dfs(node.left, sums);
        sum += dfs(node.right, sums);
        
        sums.put(sum, sums.getOrDefault(sum, 0) + 1); 
        return sum;
    }
}

class Solution2 {
    private int maxCount = 0;
    
    public int[] findFrequentTreeSum(TreeNode root) {
        HashMap<Integer, Integer> sums = new HashMap<Integer, Integer>();
        
        dfs(root, sums);
        
        List<Integer> res = new ArrayList<Integer>();
        
        for(Map.Entry<Integer, Integer> entry : sums.entrySet()) {
            if (entry.getValue() == maxCount) {
                res.add(entry.getKey());
            }
        }
        
        int[] result = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }
        return result;
    }
    
    private Integer dfs(TreeNode node, HashMap<Integer, Integer> sums) {
        if (node == null) return 0;
        
        int sum = node.val;
        sum += dfs(node.left, sums);
        sum += dfs(node.right, sums);
        
        sums.put(sum, sums.getOrDefault(sum, 0) + 1); 
        
        maxCount = Math.max(maxCount, sums.get(sum));
        
        return sum;
    }
}