LeetCode 1339. 分裂二叉树的最大乘积

约 5 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 百度 快手
标签
深度优先搜索 树 二叉树

题目描述

✅ 1339. 分裂二叉树的最大乘积

image-20260928234325982

image-20260928234325983

题意分析

删除恰好一条父子边，将整棵树分成两个非空部分，求两部分节点值之和的乘积最大能是多少。先确定最大的真实乘积，最后才对 10^9+7 取模。

切断某个非根节点与父节点之间的边时，一部分恰好是这个节点的完整子树，另一部分则是整棵树剩下的所有节点。因此可以枚举子树，不必真的修改树的连接。

解法：两次 DFS 统计子树和

核心思路

[!blue]

设整棵树的节点和为 total，某个非根节点的子树和为 sum。切断它上方的边后，两部分的和分别为 sum 和 total - sum，乘积就是 sum * (total - sum)。每条边都有唯一的下方节点，所以枚举所有非根节点就覆盖了全部切边方案。

第一遍 DFS 只计算 total。第二遍 DFS 再计算每个节点的子树和：空节点返回 0，非空节点先得到左右子树和，再加上自身值。此时当前子树已经统计完整，可以用它更新最大乘积 best，然后把子树和返回给父节点。

代码也会把根节点代入公式，此时 sum = total，乘积为 0。根没有可切的上方边，不过题目保证至少两个节点且节点值为正，真正切边的乘积一定为正，因此这个额外的 0 不影响最大值。

子树和与乘积使用 Java 的 long 或 Go 的 int64。总和最多达到 5×10^8，两部分相乘可能超出 32 位整数范围。比较过程中不能取模，因为取模会改变大小关系；只对最终 best 取模返回。

解题步骤

  1. 调用 treeSum(root)，递归累加整棵树，得到 total。
  2. 将最大乘积 best 初始化为 0，再调用第二遍 subtreeSum(root)。
  3. 对每个非空节点，递归得到左右子树和，并加上当前节点值，得到当前 sum。
  4. 用 sum * (total - sum) 更新 best，再返回 sum，供父节点继续计算。
  5. 全树处理完后，将 best 对 10^9+7 取模，并转换为题目要求的整数返回。

代码实现

class Solution {
    private static final long MOD = 1_000_000_007L;
    private long total;
    private long best;

    public int maxProduct(TreeNode root) {
        // 先得到总和，第二遍才可计算任意切边的两部分
        total = treeSum(root);
        best = 0;
        subtreeSum(root);

        return (int) (best % MOD);
    }

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

        return node.val + treeSum(node.left) + treeSum(node.right);
    }

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

        long sum = node.val + subtreeSum(node.left) + subtreeSum(node.right);

        // 先比较真实宽整数乘积，不能先取模
        best = Math.max(best, sum * (total - sum));

        return sum;
    }
}

const mod int64 = 1_000_000_007

func maxProduct(root *TreeNode) int {
    // 先得到总和，第二遍才可计算任意切边的两部分
    total := treeSum(root)
    var best int64

    var subtreeSum func(*TreeNode) int64
    subtreeSum = func(node *TreeNode) int64 {
        if node == nil {
            return 0
        }

        sum := int64(node.Val) + subtreeSum(node.Left) + subtreeSum(node.Right)
        // 先比较真实宽整数乘积，不能先取模
        if product := sum * (total - sum); product > best {
            best = product
        }
        return sum
    }

    subtreeSum(root)
    return int(best % mod)
}

func treeSum(node *TreeNode) int64 {
    if node == nil {
        return 0
    }
    return int64(node.Val) + treeSum(node.Left) + treeSum(node.Right)
}

复杂度分析

设树有 n 个节点，高度为 h。

  • 时间复杂度：$O(n)$，两次 DFS 都只访问每个节点一次，每个节点的合并与比较是常数操作。
  • 空间复杂度：$O(h)$，来自递归调用栈；两遍遍历先后进行，空间不会相乘。树退化成链时为 $O(n)$。

关键点总结

[!green]

  • 一条切边对应一个完整子树，另一侧直接用总和减去子树和得到。
  • 第一遍提供总和，第二遍以后序方式同时完成子树和统计与切边枚举。
  • 所有候选都比较真实乘积，取模仅用于最终返回。

易错点总结

[!yellow]

  • 把另一侧当成兄弟子树：切边后剩余部分还包括父节点、祖先和其他分支，必须使用 total - sum。
  • 只比较根的左右两棵子树：可以切断任意一条边，必须计算每个非根节点的子树和。
  • 在子节点返回前计算当前子树和：此时子树还未统计完整，需要先处理左右孩子。
  • 先取模再比较：模值的大小不能代表原始乘积的大小。
  • 先用 32 位整数相乘再转换：溢出在转换前就已发生，参与乘法的数本身就要使用 long 或 int64。

相似题目

题目 难度 关联与区别
663. 均匀树划分 中等 同样切一条树边分成两个部分，原题要求两边和相同，本题比较子树和与剩余和的乘积。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/94370384
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！