Given a binary tree root. Split the binary tree into two subtrees by removing 1 edge such that the product of the sums of the subtrees are maximized.
Since the answer may be too large, return it modulo 10^9 + 7.
1 2 3 4 5 6 7
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)
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)
Solution
We need to calculate the total sum of the tree and then see which root we can split, and the rest of part would be equal to total - sum(root) and then see if there have maximum product, but we need to mod operation at the end.
// time:O(n) space:O(n) long res = Integer.MIN_VALUE; long sum = 0; int mod = (int) Math.pow(10, 9) + 7; publicintmaxProduct(TreeNode root){ if (root == null) return0; sum = Sum(root); res %= mod; return (int) res; }
publiclongSum(TreeNode root){ if (root == null) return0; long left = Sum(root.left); long right = Sum(root.right); long total = left + right + root.val; // split root res = Math.max(res, total * (sum - total)); return total; }