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. Examples 1 Input:

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

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.

General idea:

Given the root node of a tree, you are required to find the most frequent subtree and. The subtree sum of a node refers to the sum of the values of all its child nodes and the child nodes of the child nodes (including the node itself). So what is the most frequent subtree sum? If there are parallel, return the values of all the highest frequencies in unlimited order. Example 1: Input:

Return [2, - 3, 4], because all values appear only once, return them in any order. Example 2: Input:

Return [2], because this sum of 2 appears twice, while - 5 only appears once. Note: you can assume that the sum of all subtrees is in the range of 32-bit int.

Idea:

In fact, it is not difficult to calculate the subtree sum of a node. You only need to use recursion to constantly judge whether its child nodes have left and right child nodes, and if so, add up their values.

However, this problem needs to compare the subtree sum of all nodes. It requires that every node encountered should take this node as the root node to calculate its subtree sum, so a new calculation should be calculated every time.

How do you record all subtrees and? Since this problem requires to find out the subtree and value with the highest frequency, you must record the number of occurrences of each value, and the method is ready to come out. Use HashMap, take subtree sum as the key and the number of occurrences as the value. For the subtree sum that has appeared, its value+1 is added to HashMap, and its value is set to 1. In this way, the sum of all subtrees can be calculated and the number of occurrences of each sum can be recorded.

Now there is only one problem left. Find the subtree and value that appear most frequently, and not necessarily only one subtree and value. Therefore, we need to traverse the HashMap and record the subtree sum with the largest number of occurrences. Because there may be multiple, we use the array to record. If we encounter the subtree sum with the largest number of current records, we will add it to the array. When there are more occurrences, we will record it again to replace the first element of the array, At the same time, an int variable num is used to record the sum of several subtrees under the maximum occurrence frequency, which can ensure that the first num array elements are the desired results after traversing the HashMap. We can take these.

This approach has been fast, beating 91%.

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    public int[] findFrequentTreeSum(TreeNode root) {
        if (root == null) return new int[0];
        
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        countSum(root, map);
        
        int[] all = new int[map.size()];
        int num = 0;
        int big = 0;
        Iterator iter = map.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry)iter.next();
            if ((int)entry.getValue() > big) {
                all[0] = (int)entry.getKey();
                num = 1;
                big = (int)entry.getValue();
            } else if ((int)entry.getValue() == big) {
                all[num] = (int)entry.getKey();
                num++;
            }
        }
        return Arrays.copyOfRange(all, 0, num);
    }
    
    public int countSum(TreeNode root, HashMap<Integer, Integer> map) {
        int sum = 0;
        sum += root.val;
        if (root.left != null) sum += countSum(root.left, map);
        if (root.right != null) sum += countSum(root.right, map);
        
        if (map.get(sum) != null) {// Let go before
            map.put(sum, map.get(sum)+1);
        } else {
            map.put(sum, 1);
        }
        return sum;
    }
}

Collection: https://github.com/Cloudox/LeetCode-Record