Most Frequent Subtree Sum

Intuition

Use DFS and add the sum of the subtree value as an additional return value to solve this problem. Mark number of each sum and in the end, find the most frequent occured sum value.

Solution


# 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: TreeNode) -> List[int]:
        if root is None:
            return []

        self.sum_count = defaultdict(int)
        self._dfs(root)

        frequency = max(self.sum_count.values())
        result = []
        for key, count in self.sum_count.items():
            if count == frequency:
                result.append(key)
        return result

    def _dfs(self, node):
        if node is None:
            return 0
        l = self._dfs(node.left)
        r = self._dfs(node.right)
        s = l + r + node.val
        self.sum_count[s] += 1
        return s