1339. Maximum Product of Splitted Binary Tree

https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/

Python

Postorder for prefix sum

from typing import Optional


class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        prefix = []
        def postorder(node):
            if not node:
                return 0
            total = postorder(node.left) + postorder(node.right) + node.val
            prefix.append(total)
            return total

        full_total = postorder(root)

        ans = 0
        for total in prefix:
            ans = max(ans, total*(full_total-total))

        return ans % (10 ** 9 + 7)