• ㊗️
• 大家
• offer
• 多多！

Problem

Given the root of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order.

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).

Example 1:

Input: root = [5,2,-3]
Output: [2,-3,4]


Example 2:

Input: root = [5,2,-5]
Output: [2]


Constraints:

• The number of nodes in the tree is in the range [1, 10^4].
• -10^5 <= Node.val <= 10^5

Code

class Solution {
int max = 0;
HashMap<Integer, Integer> map = new HashMap<>();

public int[] findFrequentTreeSum(TreeNode root) {
if(root == null) return new int[0];
helper(root);

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

int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i++){
res[i] = list.get(i);
}

return res;
}

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

int left = helper(root.left);
int right = helper(root.right);

int sum = root.val + left + right;
map.put(sum, map.getOrDefault(sum, 0) + 1);
max = Math.max(max, map.get(sum));

return sum;
}
}