LeetCode 1339 分裂二叉树的最大乘积：后序遍历与子树和深度解析

刷“每日一题”推送刷到 1339 的时候我第一反应是这题名有点唬人——“分裂二叉树的最大乘积”。点进去读完题才发现题干包装得挺复杂内核却干净得让人意外给一棵二叉树切掉一条边分成两棵子树求两棵子树节点和乘积的最大值。这道题适合正在集中刷二叉树、准备面试的人练手也适合那些想把“题目翻译成数学公式”能力练扎实的选手。它的知识点非常集中后序遍历 子树和 一个二次函数的最值。写起来不难但有几个隐藏很深的坑稍不注意就会掉进去。这篇文章把从题面拆解、代码实现到避坑细节完整过一遍最后我也会说说这道题在整个刷题地图里到底算什么位置。1. 拆题把一个“分裂操作”翻译成一个二次函数1.1 题面到底给了什么原题描述大概是这样的给你一棵二叉树的根节点 root允许你删掉一条边把树拆成两棵。设两棵树的节点和分别是 a 和 b求 a 乘以 b 的最大值最后对 10^97 取模。约束条件里藏着两个关键信息树节点数最多是 5*10^4每个节点的值在 1 到 10^4 之间。我见过不少人第一次做这题时会被“分裂”两个字带偏以为要做什么复杂的树形 DP或者以为要删除某个节点再重新拼接。其实不是。题目要的是“删边”不是“删节点”。删边之后两棵树都保持完整形状不需要任何重构操作这就让“子树和”成为了解题的核心抓手。1.2 一条边正好对应一个子树二叉树有一条非常重要的性质每条边都有一个“下端节点”。也就是说任何一条边都可以用“某个非根节点”来唯一标识。假设有一条边连接父节点 p 和子节点 v切掉这条边之后一侧是以 v 为根的整棵子树另一侧是原来的整棵树但拿掉以 v 为根的这棵子树。如果我们提前知道整棵树的总和是 S又知道以任意节点 v 为根的子树和是 sub(v)那么切掉 v 与其父节点之间的边后两部分的乘积就是product(v) sub(v) * (S - sub(v))这一步是整道题最重要的抽象。它告诉我们“分裂二叉树”这个听起来很复杂的操作本质上就是“在所有非根节点的子树和中找一个能让 x(S-x) 最大的 x”。1.3 需要枚举的候选到底有多少个一棵有 n 个节点的二叉树边数是 n-1非根节点数也是 n-1。所以“可以切的位置”天然就是线性个。我们不需要用任何高级技巧去枚举“所有可能的切割点”每个非根节点对应一条真实存在的边逐个扫描就是全枚举。这也是为什么这道题能轻松做到 O(n)而不是 O(n²)。如果你一开始想着“枚举边 每次重新算一遍子树和”那就是 O(n²) 的笨办法但只要你提前把子树和一次性算出来后面就只是一遍 O(n) 的比较。1.4 根节点不是候选却不会干扰答案根节点对应的子树和是 S但根节点上方并没有真实存在的边。如果硬把它当成候选得到的乘积是 S*(S-S)0。由于这题所有节点值都是正数0 永远不可能是最大值所以就算代码里不刻意跳过根节点结果也不会被影响。不过我在写代码时会刻意跳过根节点对应的子树和。这样做不是为了性能而是为了让代码语义更准确我们枚举的是“真实边”不是“虚拟边”。2. 后序 DFS一趟遍历完成“求和 收集”2.1 为什么必须是后序遍历子树和的定义天然决定了计算顺序sub(node) sub(node.left) sub(node.right) node.val想求当前节点的子树和必须先知道左子树的全部节点和、右子树的全部节点和。所以遍历顺序只能是左、右、根也就是后序遍历。这个顺序不是“选择”而是必须。有些同学在这里会突然绕进“前序能不能做”的牛角尖。前序可以拿到节点值但拿不到子树的汇总信息除非你再引入额外的状态或者翻转思路绕一圈回来还是后序更直白。2.2 Python 参考实现我用一个列表收集所有子树和同时用递归函数返回当前子树的和。完整代码如下class Solution: def maxProduct(self, root: Optional[TreeNode]) - int: MOD 10**9 7 sub_sums [] def dfs(node): if node is None: return 0 left dfs(node.left) right dfs(node.right) cur left right node.val sub_sums.append(cur) return cur dfs(root) total sub_sums[-1] # 后序遍历最后处理根节点所以最后一个元素是整棵树的根 best 0 # sub_sums[:-1] 排除根节点对应的“虚拟边” for s in sub_sums[:-1]: best max(best, s * (total - s)) return best % MOD代码本身很短但有几个细节值得展开。为什么sub_sums[-1]一定是整棵树的总和因为在后序遍历中根节点是最后一个被访问的节点所以它对应的子树和被追加在列表最后。这个顺序约定是我们后面安全使用sub_sums[:-1]的基础。为什么不写成for s in sub_sums然后判断s ! total也可以但[:-1]更直接。注意只有当所有节点值都是正数时才不会出现“某个非根子树的子树和恰好等于 total”的情况本题满足这个条件所以[:-1]是安全的。2.3 Java 或 C 写法需要注意的转 long如果你用 Java 刷最容易被坑的点是乘法溢出。核心代码可以这样写class Solution { long best 0; ListLong subSums new ArrayList(); public int maxProduct(TreeNode root) { dfs(root); long total subSums.get(subSums.size() - 1); for (int i 0; i subSums.size() - 1; i) { long s subSums.get(i); best Math.max(best, s * (total - s)); } return (int) (best % 1000000007L); } private long dfs(TreeNode node) { if (node null) return 0; long cur dfs(node.left) dfs(node.right) node.val; subSums.add(cur); return cur; } }注意我在 Java 版本里直接把子树和都存成了 long而不是 int。这样后面乘法就不会因为 int 溢出而出错。C 的话记得在乘法前补一个1LL *或者干脆都用 long long 存。2.4 时空复杂度时间复杂度 O(n)每个节点进入递归一次出栈时做常数次运算。空间复杂度 O(n)递归栈在最坏情况下深度是 O(n)加上存子树和的列表 O(n)。这里的最坏情况就是指树退化成一条链。链越深递归栈越危险这一点下一节专门说。3. 抛物线视角这题为什么“越接近 S/2 越好”3.1 从单调性看最优选择如果你把乘积函数单独拿出来看它就是一个标准的二次函数f(x) x(S-x) -x² Sx这个函数的图像是一条开口向下的抛物线对称轴在 xS/2。抛物线在对称轴左侧单调递增在对称轴右侧单调递减。所以直观结论就是x 越靠近 S/2乘积越大离得越远乘积越小。这个结论能直接指导我们如果存在一个子树和恰好等于 S/2那就是理论最优如果 S 是奇数或者子树和的取值不连续那就选离 S/2 最近的离散值。但要注意“选最接近 S/2”并不是一个需要单独实现的算法因为我们本来就要遍历所有候选。枚举所有非根节点是 O(n)找“最接近”同样要 O(n)。不要画蛇添足去排序或者维护什么平衡树没有必要。3.2 正数约束让边界变得干净这题节点值范围是 1 到 10^4全是正数。这带来了几个方便任意子树和 x 都严格大于 0任意子树和 x 都严格小于 S因为另一侧还有正数所以所有候选都落在抛物线的两个零点 (0, S) 之间不会跑出定义域。你可以想象如果树节点值允许负数情况会变得多麻烦子树和可能为负可能跑到 S 的右边甚至整棵树的总和也可能是负数。那时候“越接近 S/2 越好”虽然从数学上依然成立但候选的分布会让你在解释时费很多口舌。力扣把数据范围设计成全正数其实是照顾做题人。3.3 “总量 切分”是树题里的高频套路顺着这道题我想到一个更通用的做题经验。二叉树题目里经常出现“把整棵树拆成两部分让某个值最大/最小”的套路。遇到这类题第一步永远先把总量 S 求出来第二步再想怎么用一次遍历枚举所有可行切分。一旦候选被列出来怎么求最值往往是数学问题不是数据结构问题。1339 就是把这个套路压缩到了最精简的形态一个后序 DFS 收集全部子树和一个 for 循环比较乘积结束。4. 三个容易踩的坑溢出、取模时机、递归深度4.1 别用 int 算乘积先算一下这题的数据上限。总节点数最多 50000每个节点值最多 10000所以整棵树的总和 S 最多是 5*10^8。这个数还在 32 位 int 的范围内大约是 21 亿不会爆。但乘积完全不同。当 S510^8 时最理想的情况是 xS/22.510^8乘积算出来是(2.510^8)² 6.2510^16这个数字远远超过 int 的最大值 2.1*10^9。Java 和 C 里如果用 int 算乘法溢出不会报错只会默默给一个错误结果。你在本地测小样例时一切正常一提交全错而且错得莫名其妙。所以记住计算乘积时至少要用 long/long long最好一开始就把子树和存成 long。4.2 不要在比较大小阶段取模这个坑我觉得值得单独拿出来骂一次。有些题目要求结果对 1e97 取模于是有人会把取模提前做取完模再去比大小这是要命的。举例说明真实乘积是 1000000008对 1e97 取模后结果是 1真实乘积是 2对 1e97 取模后还是 2。如果比较的是取模后的结果那 1 会被判断为小于 2于是你选了乘积比真实最大值小得多的那个答案。取模是最后一步是用来“输出答案”的不是用来“比较大小”的。正确做法全程用原始乘积比大小最后一步 return 时才取模。4.3 链状树的递归深度二叉树题目的经典恐怖场景测试数据给你一条长度为几万的链。递归深度 O(n)在 Python 里默认递归上限大概是 1000遇到极端链会直接 RecursionError。力扣这道题我不确定会不会给出这么狠的测试但保险起见至少要知道处理办法。最简单的办法是在文件顶部把递归深度调大import sys sys.setrecursionlimit(300000)如果你不想依赖递归可以改成迭代后序遍历。这里给出一个参考版本用显式栈模拟“访问两次节点”的过程class Solution: def maxProduct(self, root: Optional[TreeNode]) - int: MOD 10**9 7 sub_sums [] sum_map {} stack [(root, 0)] while stack: node, state stack.pop() if state 0: stack.append((node, 1)) if node.right: stack.append((node.right, 0)) if node.left: stack.append((node.left, 0)) else: left_sum sum_map.get(node.left, 0) if node.left else 0 right_sum sum_map.get(node.right, 0) if node.right else 0 cur left_sum right_sum node.val sum_map[node] cur sub_sums.append(cur) total sub_sums[-1] best 0 for s in sub_sums[:-1]: best max(best, s * (total - s)) return best % MOD这个迭代版本就不会有递归深度限制但代价是代码明显变长。日常刷题我还是推荐递归版本面试讲起来也更清爽只有明确知道测试数据极其极端时才考虑迭代写法。4.4 一个隐蔽的递归求和错误还有一个非常容易犯的错误藏在 dfs 里。比如你本来想返回左右子树之和加当前节点值结果手滑写成return left node.val # 漏了 right这种错误在子树和偏小的时候很难发现因为最终答案可能是错的但差值不大。建议在本地跑样例时加一行调试输出打印每个节点对应的子树和和手算结果对照能很快定位到哪个分支算漏了。5. 把推理落到手算样例上5.1 官方示例一root [1,2,3,4,5,6]这棵树的结构是这样的1 / \ 2 3 / \ / 4 5 6也就是 2 的左孩子是 4右孩子是 53 的左孩子是 6右孩子为空。后序遍历时节点 4子树和 4节点 5子树和 5节点 2子树和 4 5 2 11节点 6子树和 6节点 3子树和 6 3 9节点 1子树和 11 9 1 21sub_sums 列表就是 [4, 5, 11, 6, 9, 21]S21。忽略最后一个 21候选是 [4, 5, 11, 6, 9]。逐一计算s44 * 17 68s55 * 16 80s1111 * 10 110s66 * 15 90s99 * 12 108最大是 110正好等于官方示例答案。再看抛物线角度S21S/210.5。候选里离 10.5 最近的是 11距离 0.5其次是 9距离 1.5。结果也确实选了 11。5.2 一条链的例子root [1,2,3]树的形态是1 \ 2 \ 3后序节点 3子树和 3节点 2子树和 3 2 5节点 1子树和 5 1 6S6候选 [3, 5]s33 * 3 9s55 * 1 5最大值是 9正好是把链从中间切开两边都是 3。这个例子很直观地展示了“越接近 S/2 越好”的直觉6 的一半是 3候选里恰好有 3。5.3 单节点root [7]只有一个节点树里没有任何真实边可以切。sub_sums[7]候选为空best 保持初始值 0返回 0。很多第一次做这题的人会在这里犹豫是不是应该返回某个非零值不是。题意要求分裂成两棵树没有边可以分裂乘积就是 0。把这个边界 case 想明白代码里初始值 best0 才不会被质疑。5.4 全相等节点的小批量测试我还会用 root [2,2,2,2,2] 这种全相等节点的用例再跑一遍感受一下规律。树结构不同结果可能略有不同但候选子树和的集合总是能覆盖很多整数。这种测试的意义主要是帮你验证递归是否正确而不是为了押测试点。6. 这道题在整个刷题计划里的真正价值6.1 它是“树形信息收集”的典型代表“热题 100”里虽然没有 1339但它的知识点和热题高度重合。二叉树深度、二叉树直径、二叉树最大路径和、打家劫舍 III、监控二叉树这些题的核心全是后序遍历加信息聚合。1339 是其中信息聚合方式最朴素的一种每个节点向上返回自己的子树和并且顺手把结果记到全局里。如果你能把 1339 第一次就写对说明你已经掌握了一个非常通用的递归框架。后面再遇到更复杂的树形 DP比如返回两个状态、三个状态也只是在这个框架上加东西而已。6.2 它和 124、543、968 等题的异同拿 543 二叉树的直径举例那题在每个节点做的是“左高度 右高度”更新全局直径然后向上返回 max(左高, 右高) 1。1339 每个节点做的是“左子树和 右子树和 节点值”向上返回同一个值同时用这个值和总量去更新答案。两者在结构上几乎一模一样区别只在于“信息是什么”和“怎么用来更新答案”。这就是为什么我认为 1339 是一个非常好的过渡题它比单纯的求深度难一点点但又比真正的树形 DP 简单很多。6.3 做题路线建议如果你正在按专题刷题我建议这样安排先做 104 二叉树的最大深度理解递归返回值和后序框架再做 543 二叉树的直径理解“全局变量更新答案”然后做 1339体会“子树和 数学公式”的联合最后挑战 968 监控二叉树那是最完整的树形状态 DP。这条路径从易到难非常顺滑。1339 卡在中间刚好能检验你是否真正理解了“后序递归可以携带信息向上走”这件事。我自己通常把这类题归档为“树的切分型题”。每次做到这种题第一件事不是写代码而是先把“边到子树的映射”想清楚再把目标函数写出来。1339 是一个很小的例子但它把这个思维过程压缩得很完整。如果你正在刷题可以试着用这道题检验一下能不能在五到十分钟内不借助题解独立写出 O(n) 的解法。如果能树的基础就算站稳了一小半如果不能问题多半不是递归而是“把题面翻译成公式”这一步还不熟。