LeetCode 1343. Maximum Product of Splitted Binary Tree

, , ,

Question

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.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// time:O(n) space:O(n)
    long res = Integer.MIN_VALUE;
    long sum = 0;
    int mod = (int) Math.pow(10, 9) + 7;
    public int maxProduct(TreeNode root) {
        if (root == null) return 0;
        sum = Sum(root);
        res %= mod;
        return (int) res;
    }

    public long Sum(TreeNode root) {
        if (root == null) return 0;
        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;
    }