1339. Maximum Product of Splitted Binary Tree

/**
 * Problem: LeetCode 1339 - Maximum Product of Splitted Binary Tree
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    private List<Long> allSums = new ArrayList<>();

    public int maxProduct(TreeNode root) {
        long totalSum = computeSubtreeSums(root);
        long maxProd = 0;

        for (long sum : allSums) {
            long currentProd = sum * (totalSum - sum);
            if (currentProd > maxProd) {
                maxProd = currentProd;
            }
        }

        return (int) (maxProd % 1_000_000_007L);
    }

    private long computeSubtreeSums(TreeNode node) {
        if (node == null) {
            return 0;
        }

        long currentSum = node.val + computeSubtreeSums(node.left) + computeSubtreeSums(node.right);
        allSums.add(currentSum);
        return currentSum;
    }
}

"""
Problem: LeetCode 1339 - Maximum Product of Splitted Binary Tree
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import Optional, List

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        MOD = 1_000_000_007
        all_sums: List[int] = []

        def compute_subtree_sums(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            curr_sum = node.val + compute_subtree_sums(node.left) + compute_subtree_sums(node.right)
            all_sums.append(curr_sum)
            return curr_sum

        total_sum = compute_subtree_sums(root)
        max_prod = 0

        for s in all_sums:
            prod = s * (total_sum - s)
            if prod > max_prod:
                max_prod = prod

        return max_prod % MOD

/**
 * Problem: LeetCode 1339 - Maximum Product of Splitted Binary Tree
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    vector<long long> allSums;

    long long computeSubtreeSums(TreeNode* node) {
        if (!node) {
            return 0;
        }

        long long currentSum = node->val + computeSubtreeSums(node->left) + computeSubtreeSums(node->right);
        allSums.push_back(currentSum);
        return currentSum;
    }

public:
    int maxProduct(TreeNode* root) {
        allSums.clear();
        long long totalSum = computeSubtreeSums(root);
        long long maxProd = 0;
        const int MOD = 1e9 + 7;

        for (long long sum : allSums) {
            long long currentProd = sum * (totalSum - sum);
            maxProd = max(maxProd, currentProd);
        }

        return maxProd % MOD;
    }
};

/**
 * Problem: LeetCode 1339 - Maximum Product of Splitted Binary Tree
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxProduct = function(root) {
    const MOD = 1000000007n;
    const allSums = [];

    function computeSubtreeSums(node) {
        if (!node) {
            return 0n;
        }

        const currentSum = BigInt(node.val) + computeSubtreeSums(node.left) + computeSubtreeSums(node.right);
        allSums.push(currentSum);
        return currentSum;
    }

    const totalSum = computeSubtreeSums(root);
    let maxProd = 0n;

    for (const sum of allSums) {
        const currentProd = sum * (totalSum - sum);
        if (currentProd > maxProd) {
            maxProd = currentProd;
        }
    }

    return Number(maxProd % MOD);
};