Python iterative solution


  • 0
    K
    class Solution(object):
        def findFrequentTreeSum(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            sums, counts, helper = {}, {}, {}
            max_count = 0
            if root:
                first_stack = [root]
                second_stack = []
                while first_stack:
                    current = first_stack.pop()
                    second_stack.append(current)
                    if current.left: first_stack.append(current.left)
                    if current.right: first_stack.append(current.right)
                while second_stack:
                    current = second_stack.pop()
                    subtree_sum = sums.get(current.left, 0) + sums.get(current.right, 0) + current.val
                    sums[current] = subtree_sum
                    counts[subtree_sum] = counts.get(subtree_sum, 0) + 1
                    max_count = max(max_count, counts[subtree_sum])
                    if counts.get(subtree_sum) == max_count:
                        values = helper.get(max_count, [])
                        values.append(subtree_sum)
                        helper[max_count] = values
            return helper.get(max_count, [])```

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.