Leetcode 0508 Most Frequent Subtree Sum

Problem statement

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

Solution

Traverse tree, using dsf(node) function and put values to Hash Table or even better Counter().

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def findFrequentTreeSum(self, root):
        cnt = Counter()
        
        def dfs(node):
            if not node: return 0
            ans = node.val + dfs(node.left) + dfs(node.right)
            cnt[ans] += 1
            return ans
        
        dfs(root)
        freq = cnt.most_common(1)[0][1]
        return [i for i in cnt if cnt[i] == freq]