BinarySearch 0847 Split Tree to Maximize Product

Problem statement

https://binarysearch.com/problems/Split-Tree-to-Maximize-Product/

Solution

Equal to Leetcode 1339. Maximum Product of Splitted Binary Tree.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, root):
        def dfs(node):
            if not node: return 0
            ans = dfs(node.left) + dfs(node.right) + node.val
            res.append(ans)
            return ans
        
        res = []
        dfs(root)
        sum_all = max(res)
        return max(i*(sum_all-i) for i in res)