分裂二叉树的最大乘积

问题描述

来源：LeetCode第1339题

难度：中等

给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。树至少有 2 个节点，每个节点的值在 [1, 10000] 之间。

示例 ：

问题分析

这题是删除二叉树中的一条边，让他变成两棵树，然后计算这两棵树的乘积，最后返回最大的乘积。这题我们还是自底往上的思路，首先计算二叉树中所有节点的和，然后从下往上不断的累加子树的和，相当于把子树砍掉，顺便计算砍掉的这棵子树和剩余的子树和的乘积。代码和上一题二叉树的坡度中介绍的也非常相似，来看下代码：

private long max = Integer.MIN_VALUE;//最大乘积
private long sum;// 二叉树中所有节点的和

public int maxProduct(TreeNode root) {
    sum = sum(root);
    dfs(root);
    int mod = (int) 1e9 + 7;
    return (int) (max % mod);
}

// 累加树中的所有节点值
public int sum(TreeNode node) {
    if (node == null)
        return 0;
    return node.val + sum(node.left) + sum(node.right);
}

// 返回子树和，包含当前节点
public int dfs(TreeNode root) {
    if (root == null)
        return 0;
    int leftSum = dfs(root.left);
    int rightSum = dfs(root.right);
    // 计算子树和，要加上当前节点。
    int total = leftSum + rightSum + root.val;
    // 计算两棵树的乘积，保存最大的即可。
    max = Math.max(max, (sum - total) * total);
    return total;
}

你点的每个赞，我都认真当成了喜欢