508. Most Frequent Subtree Sum

Approach 1: Recursively calculate sums

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findFrequentTreeSum(self, root):
        """
        https://leetcode.com/problems/most-frequent-subtree-sum/description/
        :type root: TreeNode
        :rtype: List[int]
        """
        di = {}
        def recurse(root):
            if root == None: return 0
            su = root.val + recurse(root.left) + recurse(root.right)
            if su not in di:
                di[su] = 0
            di[su] += 1
            return su
        recurse(root)
        re, ma = [], 0
        for i in di:
            if di[i] > ma:
                re = [i]
                ma = di[i]
            elif di[i] == ma:
                re.append(i)
        return re

We will recursively calculate the sums for each subtree, and keep a dictionary to keep track of the number of times a sum has occurred. Then we can just iterate through the list and return the list of those values that occur maximum number of times

Time Complexity: O(N), where N is the total number of nodes

Space Complexity: O(N)