Given the root of a binary tree, split the binary tree into two subtrees by removing one edge such that the product of the sums of the subtrees is maximized.
Return the maximum product of the sums of the two subtrees. Since the answer may be too large, return it modulo 109 + 7.
Note that you need to maximize the answer before taking the mod and not after taking it.
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)
Constraints:
[2, 5 * 104].1 <= Node.val <= 104This method involves two main traversals of the tree:
1. Calculate the total sum of the tree using a post-order traversal.
2. During another post-order traversal, calculate the sum of each subtree and evaluate the potential product if split at that point.
This solution performs a post-order traversal to first calculate the total sum of the tree. It uses another post-order traversal to calculate each subtree sum, and checks the product of the sum of the current subtree and the sum of the rest of the tree. The maximum product found during this traversal is returned.
Java
C++
JavaScript
Time Complexity: O(N), where N is the number of nodes. The algorithm performs a constant amount of work for each node.
Space Complexity: O(H), where H is the height of the tree. This space is used by the call stack during recursion.
This approach uses an iterative post-order traversal using a stack to avoid recursion and concurrently calculate subtree sums and products. Carefully pushing nodes onto a stack and maintaining metadata to track progress and necessary calculations allow for this approach.
This C# implementation uses a stack for iterative traversal in a post-order manner. With each loop iteration, it processes nodes and calculates sub-tree sums dynamically, treating the stack as a simulacrum for recursion. This allows for efficient computation without hitting recursion limits, and still evaluates maximum products as it iterates through subtree sums.
Time Complexity: O(N), due to each node being evaluated once by following its sequence to the stack until processed.
Space Complexity: O(H), where H is the height of the tree since the stack depth follows the path of the tree.
| Approach | Complexity |
|---|---|
| Recursive Post-order Traversal | Time Complexity: O(N), where N is the number of nodes. The algorithm performs a constant amount of work for each node. Space Complexity: O(H), where H is the height of the tree. This space is used by the call stack during recursion. |
| Iterative Post-order Traversal with Stack | Time Complexity: O(N), due to each node being evaluated once by following its sequence to the stack until processed. Space Complexity: O(H), where H is the height of the tree since the stack depth follows the path of the tree. |
Leetcode 1339. Maximum Product of Splitted Binary Tree • Fraz • 7,130 views views
Watch 9 more video solutions →Practice Maximum Product of Splitted Binary Tree with our built-in code editor and test cases.
Practice on FleetCode