Most Frequent Subtree Sum

Question

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.

Solution

這題思路其實滿直接的，但我花了點時間才寫出來。我的方法是用 map 記錄數字出現的頻率，然後最後找到出現最多次的加進 array 裡。自己的寫法有幾個需要注意的地方：

1. 我先用了 helper 函數記錄所有 (sum, frequent)。但在這個 helper 裡面再用了一個 recursion function 去 bottom-up 計算 subarray sum
2. 用兩個 for loop 找出 most frequent 跟 sum，並加到 list 裡面，最後再 return array 型態

我覺得能夠優化的地方為兩次的 recursion 還有兩個 for loop

optimal

用 global 的 map 跟 maxCount，在 recursion 時去 update 這兩個值，就可以把 recursion 跟 for loop 減少變成各一次

Map<Integer, Integer> map;
    int maxCount;
    public int[] findFrequentTreeSum(TreeNode root) {
        if (root == null) {
            return new int[0];
        }

        map = new HashMap<Integer, Integer>(); // <sum, frequent>
        helper(root);
        List<Integer> list = new ArrayList<Integer>();
        for (int num : map.keySet()) {
            if (map.get(num) == maxCount) {
                list.add(num);
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }

        return res;
    }

    public int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = helper(root.left);
        int right = helper(root.right);
        int sum = left + right + root.val;
        int count = map.getOrDefault(sum, 0) + 1;

        map.put(sum, count);
        maxCount = Math.max(maxCount, count);
        return sum;
    }