Skip to content

1339. Maximum Product of Splitted Binary Tree 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  int maxProduct(TreeNode* root) {
    constexpr int kMod = 1'000'000'007;
    long ans = 0;
    vector<int> allSums;
    const long totalSum = treeSum(root, allSums);

    for (const long sum : allSums)
      ans = max(ans, sum * (totalSum - sum));

    return ans % kMod;
  }

 private:
  int treeSum(TreeNode* root, vector<int>& allSums) {
    if (root == nullptr)
      return 0;

    const int leftSum = treeSum(root->left, allSums);
    const int rightSum = treeSum(root->right, allSums);
    const int sum = root->val + leftSum + rightSum;
    allSums.push_back(sum);
    return sum;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public int maxProduct(TreeNode root) {
    final int kMod = 1_000_000_007;
    long ans = 0;
    List<Integer> allSums = new ArrayList<>();
    final long totalSum = treeSum(root, allSums);

    for (final long sum : allSums)
      ans = Math.max(ans, sum * (totalSum - sum));

    return (int) (ans % kMod);
  }

  private int treeSum(TreeNode root, List<Integer> allSums) {
    if (root == null)
      return 0;

    final int leftSum = treeSum(root.left, allSums);
    final int rightSum = treeSum(root.right, allSums);
    final int sum = root.val + leftSum + rightSum;
    allSums.add(sum);
    return sum;
  }
}