LeetCode : 508. Most Frequent Subtree Sum

[congr]

https://leetcode.com/problems/most-frequent-subtree-sum/

[congr]

/**
 * 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> map = new HashMap();
        max = 0;

        postOrder(root, map);
        List<Integer> list = new ArrayList<>();
        for (Integer key : map.keySet()) {
            int freq = map.get(key);
            if (freq == max) list.add(key);
        }

        int i = 0;
        int[] res = new int[list.size()];
        for (int n : list) res[i++] = n;

        return res;
    }

    int max;
    int postOrder(TreeNode root, Map<Integer, Integer> map) {
        if (root == null) return 0;

        int left = postOrder(root.left, map);
        int right = postOrder(root.right, map);

        int sum = root.val + left + right;
        int freq = map.merge(sum, 1, Integer::sum);

        max = Math.max(max, freq);
        return sum;
    }
}