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

2026-03-11 HGNULB 约 6 分钟

文章信息 8 个分类 3 个标签

分类

题目描述

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

题意分析

给一棵二叉树，要求删掉其中一条边，把树分成两棵互不相连的子树，使这两部分各自节点值之和的乘积最大，返回这个最大乘积对 $10^9 + 7$ 取模的结果。

有个结构性事实要先看清：二叉树里每条边都唯一对应它下端的那个节点。删掉这条边，分出来的一部分恰好是「以该下端节点为根的整棵子树」，另一部分是剩下的所有节点。所以「枚举边」和「枚举非根节点」是一回事。

约束信号：节点数上限 $5 \times 10^4$，每个节点的值在 $[1, 10^4]$。总和最大约 $5 \times 10^8$，本身还在 32 位范围内，但两部分的乘积最大可达 $(2.5 \times 10^8)^2 = 6.25 \times 10^{16}$，远超 32 位上限，必须用 64 位整数承载。

边界情况：取模只能在最后一步做，因为取模会破坏数值的大小关系，中途取模会导致比较结果错乱。另外，如果把根节点也纳入枚举，对应的「另一部分」是空树，和为 0，乘积为 0，由于所有节点值都为正，这个 0 不会成为最大值，因此无需特意排除。

解法：两次 DFS 统计子树和

核心思路

树中每条可删除的边，都唯一对应它下方的子节点 v。删除这条边后，一部分是以 v 为根的完整子树，另一部分是其余节点。因此“枚举所有切边”可以转换成“枚举所有非根节点的子树和”。

设整棵树的节点和为 $T$，某个节点的子树和为 $s$，切开它与父节点之间的边后，两部分的和分别为 $s$ 和 $T-s$，乘积为
\[f(s)=s(T-s)=\frac{T^2}{4}-\left(s-\frac{T}{2}\right)^2.\]
所以子树和越接近 $T/2$，乘积越大。但子树和由树结构决定，不能任意取值，仍需枚举每个节点的实际子树和。

子树和满足 sub(node) = node.val + sub(left) + sub(right)，天然适合后序 DFS。先用第一趟 DFS 求总和 total；第二趟 DFS 自底向上计算每个 subSum，并用 subSum * (total - subSum) 更新最大值。

第二趟 DFS 的不变量是：dfs(node) 返回时，返回值等于 node 的完整子树和，且 best 已比较过这棵子树内所有节点对应的切边。根节点没有父边，但把它代入只得到 $T(T-T)=0$；节点值均为正时不会影响最大值，代码无需额外特判。

正确性依据：

每条边与其下端节点一一对应，因此遍历所有节点不会漏掉任何合法切分。

后序递归先得到左右子树的准确和，再加当前值，所以每次计算的 subSum 都正确；另一部分必为 total - subSum。

best 对每个合法切分的真实乘积取最大值，因此遍历结束时就是全局最大乘积。取模只改变返回形式，不参与最优方案比较。

解题步骤

第一趟 DFS 求整棵树的节点和 total。

将最大乘积 best 初始化为 0，并使用 64 位整数保存总和与乘积。

第二趟 DFS 按后序计算：空节点返回 0，非空节点返回“当前值 + 左子树和 + 右子树和”。

得到每个 subSum 后，计算 subSum * (total - subSum) 并更新 best。

所有节点处理完后，返回 best % 1_000_000_007。

以 [1,2,3,4,5,6] 为例，总和为 21。非根节点的子树和依次包含 4、5、11、6、9，对应乘积为 68、80、110、90、108；最大值 110 来自切下和为 11 的节点 2 子树。

代码实现

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 各访问每个节点一次，常数 2 不影响渐进复杂度。

空间复杂度：$O(h)$，来自递归栈；平衡树为 $O(\log n)$，链状树最坏为 $O(n)$。

关键点总结

删除父子边后，被切下的一部分一定是子节点对应的完整子树。

已知总和与一个子树和，另一部分直接用 total - subSum 得到，无需再次遍历。

后序遍历保证计算父节点前，左右子树和已经确定。

最大乘积对应最接近总和一半的可用子树和，但仍要枚举实际存在的子树。

面试时要主动说明两类数值处理：乘积用 64 位，取模必须放在最大值确定之后。

易错点总结

用 32 位整数计算乘积：总和最大为 $5\times10^8$，乘积可达约 $6.25\times10^{16}$。Java 必须在相乘前使用 long，Go 使用 int64。

比较前先取模：较大的原始乘积取模后可能更小，最大值关系会被破坏；只能对最终 best 取模。

用先序值充当子树和：访问父节点时孩子尚未统计，得到的只是部分和；子树聚合必须后序计算。

每枚举一个节点就重新求一次子树和：链状树会退化到 $O(n^2)$；让 DFS 返回子树和即可一次算完。

把另一部分误写成兄弟子树和：切开深层节点时，另一部分还包含祖先及祖先的其他分支，正确值始终是 total - subSum。

递归深度被忽略：链状树的调用栈深度可达 $n$。面试中应说明这一点；若目标运行环境栈较小，再改成显式栈的后序遍历。

相似题目

题目	难度	考察点
543. 二叉树的直径	简单	后序返回深度，答案在节点处横向合并
437. 路径总和 III	中等	根到当前节点的前缀和配合哈希表计数
124. 二叉树中的最大路径和	困难	值可为负，返回值需与更新值区分并做截断
1373. 二叉搜索子树的最大键值和	困难	后序需同时上传和、极值与合法性多个字段