Maximum Product of Splitted Binary Tree

Intuition

Use 2 DFS to solve this problem. The first DFS would get the sum of all nodes. And the second DFS would be used to get the product of removing each edge.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxProduct(self, root: TreeNode) -> int:
        total = self._dfs_sum(root)
        self.max_product = 0
        self._dfs_product(root, total)
        return self.max_product % (10 ** 9 + 7)

    def _dfs_sum(self, node):
        if node is None:
            return 0
        return self._dfs_sum(node.left) + self._dfs_sum(node.right) + node.val

    def _dfs_product(self, node, total):
        if node is None:
            return 0
        l = self._dfs_product(node.left, total)
        r = self._dfs_product(node.right, total)
        s = l + r + node.val
        product = (total - s) * s
        self.max_product = max(self.max_product, product)
        return s