1339. Maximum Product of Splitted Binary Tree (Medium) - TengnanYao/daily_leetcode GitHub Wiki

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxProduct(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        sums = set()
        def getSum(node):
            s = 0
            if node:
                s += node.val + getSum(node.left) + getSum(node.right)
            sums.add(s)
            return s
        total = getSum(root)
        result = 0
        for num in sums:
            result = max(result, num * (total - num))
        return result % (10 ** 9 + 7)