分裂二叉树的最大乘积

// 题目思路：
// 1. 计算整个二叉树的总和。
// 2. 通过递归遍历每个节点，计算每个子树的和。
// 3. 每次计算出一条边的删除后，两个子树和的乘积，并更新最大乘积。
// 4. 返回最大乘积对10^9 + 7取模的结果。

import java.util.*;
import java.util.stream.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private long totalSum = 0;
    private long maxProduct = 0;
    private static final int MOD = 1_000_000_007;

    public int maxProduct(TreeNode root) {
        // 计算总和
        totalSum = treeSum(root);
        // 计算最大乘积
        calculateMaxProduct(root);
        return (int) (maxProduct % MOD);
    }

    private long treeSum(TreeNode node) {
        if (node == null) return 0;
        return Stream.of(node.val, treeSum(node.left), treeSum(node.right)).mapToLong(Long::longValue).sum();
    }

    private long calculateMaxProduct(TreeNode node) {
        if (node == null) return 0;
        long subTreeSum = Stream.of(node.val, calculateMaxProduct(node.left), calculateMaxProduct(node.right)).mapToLong(Long::longValue).sum();
        long product = subTreeSum * (totalSum - subTreeSum);
        maxProduct = Math.max(maxProduct, product);
        return subTreeSum;
    }
}