Leetcode 508 Solution

This article provides solution to leetcode question 508 (most-frequent-subtree-sum)
Categories:
Tags:
Access this page by simply typing in "lcs 508" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/most-frequent-subtree-sum

Solution

# 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: Optional[TreeNode]) -> List[int]:
        m = collections.defaultdict(int)

        def dfs(node):
            if node is None:
                return 0

            v = node.val + dfs(node.left) + dfs(node.right)
            m[v] += 1
            return v

        dfs(root)

        arr = [(-v, k) for k, v in m.items()]
        arr.sort()

        ans = []
        for i in range(len(arr)):
            if arr[i][0] != arr[0][0]:
                break
            ans.append(arr[i][1])

        return ans