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.
1class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int val) { this.val = val; }
6}
7
8public class Solution {
9 private long maxProduct = 0;
10 private long totalTreeSum = 0;
11 private static final int MOD = (int)1e9 + 7;
12
13 public int maxProduct(TreeNode root) {
14 totalTreeSum = totalSum(root);
15 findMaxProduct(root);
16 return (int)(maxProduct % MOD);
17 }
18
19 private long totalSum(TreeNode node) {
20 if (node == null) return 0;
21 return node.val + totalSum(node.left) + totalSum(node.right);
22 }
23
24 private long findMaxProduct(TreeNode node) {
25 if (node == null) return 0;
26 long subTreeSum = node.val + findMaxProduct(node.left) + findMaxProduct(node.right);
27 maxProduct = Math.max(maxProduct, subTreeSum * (totalTreeSum - subTreeSum));
28 return subTreeSum;
29 }
30}In this Java solution, we calculate the total sum of the binary tree first. Then, through recursive functions, similar to the previous approach, we calculate the sub-tree sum at each node and keep track of the maximum possible product calculated from the subtree sums.
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.