[Leetcode] Problem 1339 - Maximum Product of Splitted Binary Tree

Posted on | In ,

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.

Example

No.1

00wDf0.png

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)

No.2

00wO7d.png

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)

No.3

Input: root = [2,3,9,10,7,8,6,5,4,11,1]

Output: 1025

No.4

Input: root = [1,1]

Output: 1

Constraints

  • Each tree has at most 50000 nodes and at least 2 nodes.
  • Each node’s value is between [1, 10000].

Code

1
2
3
4
5
6
7
8
9
10
11
12
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private long sum = 0;
private long product = 0;

public int maxProduct(TreeNode root) {
    sum = traverse(root, true);
    traverse(root, false);
    return (int) (product % (1e9 + 7));
}

private long traverse(TreeNode root, boolean isSum) {
    if (root == null)
        return 0;

    long left = traverse(root.left, isSum);
    long right = traverse(root.right, isSum);

    if (!isSum) {
        long max = Math.max((sum - left) * left, (sum - right) * right);
        product = Math.max(product, max);
    }

    return root.val + left + right;
}