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:

  5
 /  \
2   -3

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


Examples 2
Input:

  5
 /  \
2   -5

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.

Difficulty: interview

Starter code:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def findFrequentTreeSum(self, root: TreeNode) -> List[int]:
        

Solutions:
class Solution:
 
     def findFrequentTreeSum(self, root):
         self.sums = []
         if not root:
             return []
         self.traverse(root)
         res = collections.Counter(self.sums)
         frequent = max(res.values())
         return [x for x in res if res[x] == frequent]
 
 
     def traverse(self, root):
         if not root:
             return 0
         
         self_sum = root.val + self.traverse(root.left) + self.traverse(root.right)
 
         self.sums.append(self_sum)
         return self_sum


# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def findFrequentTreeSum(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         if root == None: return []
         m = collections.defaultdict(int)
         self.helper(root, m)
         max_value = max(m.values())
         res = []
         for v in m.keys():
             if m.get(v) == max_value:
                 res.append(v)
         return res
         
     def helper(self, node, m):
         if not node:
             return 0
         left, right = self.helper(node.left, m), self.helper(node.right, m)
         m[node.val+left+right]+=1
         return node.val + left + right

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 from collections import defaultdict
 
 class Solution:
   def findFrequentTreeSum(self, root):
     """
     :type root: TreeNode
     :rtype: List[int]
     """
     def get_sum(node):
       if node == None:
         return 0
       sum = node.val + get_sum(node.left) + get_sum(node.right)
       sum_freq[sum] += 1
       return sum
 
     # Calculate sum for all subtrees and save them in dict `sum_freq`
     sum_freq = defaultdict(lambda: 0)
     get_sum(root)
     if not sum_freq:
       return []
     # Filter sums by the highest frequency
     max_freq = max(sum_freq.values())
     return [sum for (sum, freq) in sum_freq.items() if freq == max_freq]
 


# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def findFrequentTreeSum(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         if root == None: return []
         m = collections.defaultdict(int)
         self.helper(root, m)
         max_value = max(m.values())
         res = []
         for v in m.keys():
             if m[v] == max_value:
                 res.append(v)
         return res
         
     def helper(self, node, m):
         if not node:
             return 0
         left, right = self.helper(node.left, m), self.helper(node.right, m)
         m[node.val+left+right]+=1
         return node.val + left + right

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 from collections import defaultdict
 
 class Solution:
     def findFrequentTreeSum(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         if not root:
             return []
         self.convert_tree(root)
         self.counter = defaultdict(int)
         self.dfs(root)
         
         max_ct = max(self.counter.values())
         return [k for k, ct in self.counter.items() if ct == max_ct]
 
     def convert_tree(self, node):
         """
         Convert each node's 'val' into it's subtree sum
         """
         if not node:
             return
         
         if node.left:
             self.convert_tree(node.left)
             node.val += node.left.val
         if node.right:
             self.convert_tree(node.right)
             node.val += node.right.val
     
     def dfs(self, node):
         if node:
             self.counter[node.val] += 1
             self.dfs(node.left)
             self.dfs(node.right)
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def findFrequentTreeSum(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         res = dict()
         def helper(root):
             if not root:
                 return 0
             val = root.val + helper(root.left) + helper(root.right)
             if val in res:
                 res[val] += 1
             else:
                 res[val] = 1
             return val
             
         helper(root)
         if not res:
             return []
         
         max_val = max(res.values())
         return [k for k, v in res.items() if v == max_val]

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def findFrequentTreeSum(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         if not root: return []
         D = dict()
         def AccuTree(root):
             if not root: return 0
             leftA = AccuTree(root.left)
             rightA = AccuTree(root.right)
             Accu = leftA + rightA + root.val
             if D.get(Accu): D[Accu] += 1
             else: D[Accu] = 1
             return Accu
         AccuTree(root)
         maxVal = max(D.values())
         return [x for x in D.keys() if D[x] == maxVal]

from collections import defaultdict
 # Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     """
     :type root: TreeNode
     :rtype: map{sum:int : frequency:int} 
     """
     def __init__(self):
         self._iter = 0
     def getAllSums(self, root):
         if not root:
             return defaultdict(int), 0
         all_sums, left_sum = self.getAllSums(root.left)
         all_right_sums, right_sum = self.getAllSums(root.right)    
         # mege both maps
         for key,val in all_right_sums.items():
             all_sums[key] += val
         cur_sum = right_sum + root.val + left_sum
         all_sums[cur_sum] += 1
         return all_sums, cur_sum
         
     def findFrequentTreeSum(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         all_sums,_ = self.getAllSums(root)
         result = []
         max_occurence = 0
         for key,val in all_sums.items():
             max_occurence = max(max_occurence,val)
         for key,val in all_sums.items():
             if val == max_occurence:
                 result.append(key)
         return result
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
   def findFrequentTreeSum(self, root):
     from collections import defaultdict
     f = defaultdict(int)    
     def treeSum(root):
       if not root: return 0
       s = root.val + treeSum(root.left) + treeSum(root.right)
       f[s] += 1   
       return s
     treeSum(root)
     ans = []
     if not f: return ans    
     max_freq = max(f.values())    
     for s in f:
       if f[s] == max_freq: 
         ans.append(s)
     return ans