Leetcode 1465 Solution
This article provides solution to leetcode question 1465 (maximum-product-of-splitted-binary-tree)
Access this page by simply typing in "lcs 1465" in your browser address bar if you have bunnylol configured.
Leetcode Question Link
https://leetcode.com/problems/maximum-product-of-splitted-binary-tree
Solution
# 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: TreeNode) -> int:
total = 0
ans = 0
def dfs(node):
nonlocal total
nonlocal ans
if not node: return 0
left_sum, right_sum = dfs(node.left), dfs(node.right)
ans = max(ans, left_sum * (total - left_sum), right_sum * (total - right_sum))
return node.val + left_sum + right_sum
total = dfs(root)
dfs(root)
return ans % (10**9 + 7)