subtreesum.py

#
# Binary trees are already defined with this interface:
# class Tree(object):
#   def __init__(self, x):
#     self.value = x
#     self.left = None
#     self.right = None
def mostFrequentSum(root):
    if root is None:
        return []
    sums = {}
    toSee = [(root, [])]
    while toSee:
        root, parents = toSee.pop()
        # print(root.value, [a.value for a in parents])
        sums[root] = root.value
        for p in parents:
            sums[p] += root.value
        if root.left:
            toSee.append((root.left, parents + [root]))
        if root.right:
            toSee.append((root.right, parents + [root]))
    sums = list(sums.values())
    counts = {}
    for a in sums:
        if a not in counts:
            counts[a] = 0
        counts[a] += 1
    counts = list(counts.items())
    # print(counts)
    maxval = max(counts, key=lambda x: x[1])[1]
    # print(maxval)
    counts = list(map(lambda x: x[0], filter(lambda x: x[1] == maxval, counts)))
    # print(counts)
    counts.sort()
    return counts