LeetCode

leetcode_508.py

# 508. Most Frequent Subtree Sum
# https://leetcode.com/problems/most-frequent-subtree-sum/
# Easy

# 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]:

    def dfs(root):
      if not root:
        return 0
      
      nonlocal max_freq

      this_sum = dfs(root.left) + dfs(root.right) + root.val

      if this_sum not in sum_freqs:
        sum_freqs[this_sum] = 1
      else:
        sum_freqs[this_sum] += 1
      
      if sum_freqs[this_sum] == max_freq:
        ans.append(this_sum)
      elif sum_freqs[this_sum] > max_freq:
        max_freq += 1
        ans.clear()
        ans.append(this_sum)

      return this_sum
      
    sum_freqs = {}
    max_freq = 0
    ans = []

    dfs(root)

    return ans