#1339

Maximum Product of Splitted Binary Tree

specialist · 780 · lc medium +31 · verified · 55.6% accepted · 3,574 likes · top 49%

Description

Given the root of a binary tree, remove exactly one edge to split it into two subtrees. Return the maximum possible product of the two subtree sums, modulo 10⁹ + 7. Maximize the product before applying the modulo.

Example 1:

Input: root = [1,2,3,4,5,6]

Output: 110

Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)

Example 2:

Input: root = [1,null,2,3,4,null,null,5,6]

Output: 90

Explanation: Remove the red edge and get 2 binary trees with sum 15 and 6.Their product is 90 (15*6)

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int: