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

maximumProductOfSplitBinaryTree.py

# Bottom-up DFS. Accepted. 
# O(n)
class Solution:
    def maxProduct(self, root: TreeNode) -> int:

        treeSum = root.val + self.sumTree(root.left) + self.sumTree(root.right)
        result = 0

        def dfs(root):
            
            if root is None: return 0
            
            nonlocal result
            
            lSum = dfs(root.left)
            rSum = dfs(root.right)
            breakLeft = lSum * (treeSum - lSum)
            breakRight = rSum * (treeSum - rSum)
            
            result = max(result, breakLeft, breakRight)
            
            return lSum + rSum + root.val
    
        dfs(root)
        return result%(pow(10, 9)+7)
    
    def sumTree(self, root):
        return (root.val + self.sumTree(root.left) + self.sumTree(root.right)) if root else 0
      
# Top-Down recursive. TLE
# O(n^2)? Because every parent node visits every child node independently?
class Solution:
    def maxProduct(self, root: TreeNode) -> int:
        
        rSum = self.sumTree(root.right)
        lSum = self.sumTree(root.left)
        
        breakLeft = (root.val + rSum) * lSum
        breakRight = (root.val + lSum) * rSum
        deepLeft = self.maxProdWithParent(root.left, rSum + root.val)
        deepRight = self.maxProdWithParent(root.right, lSum + root.val)
        result = max(breakLeft, breakRight, deepLeft, deepRight)
        
        return result%(pow(10, 9)+7)
    
    def maxProdWithParent(self, root, parentSum):
        
        if not root: return 0
        rSum = self.sumTree(root.right)
        lSum = self.sumTree(root.left)
        
        breakParent = parentSum * (lSum + rSum + root.val)
        deepLeft = self.maxProdWithParent(root.left, parentSum + rSum + root.val)
        deepRight = self.maxProdWithParent(root.right, parentSum + lSum + root.val)
        
        return max(breakParent, deepLeft, deepRight)
    
    def sumTree(self, root):
        return (root.val + self.sumTree(root.left) + self.sumTree(root.right)) if root else 0