Sponsored
Sponsored
This 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.
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.
1import sys
2sys.setrecursionlimit(10**6)
3
4MOD = 10**9 + 7
5
6class TreeNode:
7 def __init__(self, val=0, left=None, right=None):
8 self.val = val
9 self.left = left
10 self.right = right
11
12class Solution:
13 def maxProduct(self, root: TreeNode) -> int:
14 # Helper function to calculate total sum
15 def totalSum(node):
16 if not node:
17 return 0
18 return node.val + totalSum(node.left) + totalSum(node.right)
19
20 total = totalSum(root)
21 self.max_product = 0
22
23 # Helper function to calculate sub tree sums and max product
24 def findMaxProduct(node):
25 if not node:
26 return 0
27 sub_tree_sum = node.val + findMaxProduct(node.left) + findMaxProduct(node.right)
28 # Maximize the product of (total - sub_tree_sum) * sub_tree_sum
29 self.max_product = max(self.max_product, sub_tree_sum * (total - sub_tree_sum))
30 return sub_tree_sum
31
32 findMaxProduct(root)
33
34 return self.max_product % MODThis 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.
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.
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.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
6 this.val = val;
7 this.left = left;
this.right = right;
}
}
public class Solution {
private const int MOD = 1000000007;
private long maxProduct = 0;
private long totalSum = 0;
public int MaxProduct(TreeNode root) {
totalSum = GetTotalSum(root);
Stack<(TreeNode node, long sum)> stack = new Stack<(TreeNode, long)>();
stack.Push((root, 0));
while (stack.Count > 0) {
var (node, subTreeSum) = stack.Pop();
if (node != null) {
long currentSum = node.val + subTreeSum;
if (node.left == null && node.right == null) {
maxProduct = Math.Max(maxProduct, currentSum * (totalSum - currentSum));
}
else {
stack.Push((node.left, currentSum));
stack.Push((node.right, currentSum));
}
}
}
return (int)(maxProduct % MOD);
}
private long GetTotalSum(TreeNode node) {
if (node == null) return 0;
return node.val + GetTotalSum(node.left) + GetTotalSum(node.right);
}
}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.