每次刷力扣遇到二叉树的题目我第一反应都是先在心里叹口气——树的题目写起来不算长但思路一旦歪了调试起来真的是折磨。今天的每日一题是分裂二叉树的最大乘积题号1339难度中等。这题表面上看着人畜无害不就是切一条边算乘积嘛但真动手写的时候容易在数据溢出、算法复杂度、以及拆了之后剩下那边怎么算几个地方栽跟头。这篇文章我就把这道题从暴力思路到最终解法完整拆开讲包括我为啥一开始在DFS的返回值上纠结了半小时以及最终的代码到底怎么落地。先说这题到底在干啥。给你一棵二叉树的根节点你只能删掉一条边把这棵树分成两棵独立的子树然后分别算出两棵子树的节点值之和最后把这两个和相乘要求这个乘积尽可能大。答案要对10^9 7取模后返回。注意题目说的是节点值之和相乘不是节点值本身相乘这个别理解偏了。这题非常适合当每日一题因为它考察的点很基础也很核心树的遍历、子树和的计算、以及对乘法的基本拆解。无论你是刚开始刷二叉树的新手还是准备面试正在疯狂刷题的老手这题都值得花点时间吃透。它的解法本身不复杂但里面有几个细节习惯平时不注意的话笔试现场大概率要翻车。1. 先从最笨的思路说起枚举每一条边到底行不行很多人的第一反应是这题不就是把每条边都切一遍然后分别计算两边的和再求乘积取最大值吗听起来很简单但真按这个思路去写你马上会遇到一个很尴尬的问题——切完一条边之后你怎么知道切出来的两个部分分别的和是多少我一开始就是这么想的写一个递归函数每次传入当前这条边已经被删除的状态然后分别统计左右两边的节点和。这相当于模拟删边之后再遍历整棵树来求和。如果树的节点数是n那你就要枚举n-1条边每删一条边都要对整棵树重新做一次遍历求和整体复杂度就变成了O(n²)。在LeetCode上这题给的节点数上限是5万。如果写O(n²)的暴力代码虽然小数据量跑起来没问题但一遇到大数据的测试用例基本就是超时的命。树的n²和数组的n²还不一样树的递归本身有函数调用开销再加上反复遍历常数系数比数组的暴力循环还要大不少。所以结论很直接枚举每条边这条路只能作为一个我先确认一下题意没理解错的验证手段不能当作最终解法。真正高效的做法必须先把整棵树的总和求出来然后利用DFS过程中自然得到的子树和去计算每一条边对应的分裂状态这样一次遍历就能拿到所有可能切割位置的乘积候选值。这个思路说白了就是一句话你和一个人并肩站着想知道你俩距离多少不需要拿尺子从中间量过去你只需要量出你的位置和总长度剩下那段自然就出来了。树的边切割也是同理。2. 数学上的关键一步把切完之后再算变成提前算好这题能不能做出来基本就看你有没有转过这个弯一棵树的总和是固定不变的假设你在某个节点切断了它和父节点之间的那条边那么这个节点所在的子树的和我们记为sum另外一部分也就是原树刨去这棵子树后的剩余部分的和就是total - sum。两部分的乘积就是sum * (total - sum)。这个式子一出来问题就变成了在整棵树里找到一棵子树使得这棵子树的和sum满足sum * (total - sum)最大。等一下这里有个细节要注意。题目说的是删掉一条边之后分成两棵子树所以你切的位置其实是在某个节点和它的父节点之间。换句话说这个子树必须是某个节点连同它的全部后代节点不能是随便拼凑的部分节点。这个认知很重要很多人写着写着一不小心就把局面扩大到任意节点集合了。于是解法框架就非常清晰了先遍历一遍整棵树算出总和total。再做一次DFS遍历每个节点的时候算出以这个节点为根的子树和cur。对每个cur计算乘积cur * (total - cur)维护一个最大值。因为题目要求对10^9 7取模所以最终的答案要模这个数。这里还有一个隐藏的比较深的点如果你每一步都对cur * (total - cur)取模再比较大小其实是错的。因为取模运算会破坏原本的数值大小关系。假设两个乘积分别是1000000010和1000000000前者取模后变成3后者还保持1000000000如果你比较的是取模后的值就会错误地认为后者更大。正确的做法是在DFS过程中用原始的cur * (total - cur)去比较大小维护一个原始意义上的最大值maxProduct。等遍历结束之后再用maxProduct % (10^9 7)作为最终返回值。这个地方我在写第一版代码的时候没注意结果答案莫名其妙出错排查了很久才发现是取模时机搞错了。关于数据溢出也值得多提一嘴。节点的value范围是1到10000节点数最多50000所以total最大也就是5亿这个范围int其实还扛得住Java的int上限是21亿左右。但一旦算乘积total * total那就是25亿级别已经超过int范围了所以必须用long来保存乘积和中间结果。刷题用Python的同学没这个烦恼但用Java、C的就要特别小心漏了long很可能就是Wrong Answer而不是Time Limit Exceeded。3. 核心代码拆解两种DFS写法和它们的天坑解法思路清楚了代码实现其实很简单。不过这里我还是想把两种常见的DFS写法都摆出来因为我在写的时候发现两种写法各有各的坑理解了它们你对树的递归理解会上一个台阶。先看第一种写法也是最自然的一种两次DFS第一次求总和第二次扫描所有可能的切割点。class Solution { private long total 0; private long maxProduct 0; public int maxProduct(TreeNode root) { total sumTree(root); dfs(root); return (int) (maxProduct % 1000000007); } private long sumTree(TreeNode node) { if (node null) return 0; return node.val sumTree(node.left) sumTree(node.right); } private long dfs(TreeNode node) { if (node null) return 0; long leftSum dfs(node.left); long rightSum dfs(node.right); long currentSum leftSum rightSum node.val; // 当前子树和对应一条从当前节点到父节点的边 // 但注意根节点没有父节点这条边不存在所以要排除 if (node ! root) { long product (total - currentSum) * currentSum; maxProduct Math.max(maxProduct, product); } return currentSum; } }等等上面这个代码有bug。我在dfs函数里用node ! root来判断是否为根节点但是root这个变量怎么获取另外如果我在dfs方法里已经对左右子树递归了那么其实我可以在递归返回的过程中自然得到每个子树的整棵子树和根节点本身在递归返回时也能被处理只是需要判断不要切在根节点上方的虚拟边。正确的判断方式是在主函数里记录root引用或者在dfs中当currentSum等于total时跳过——但这样也不严谨因为可能存在某个子树的和恰好等于total吗不可能因为节点值都是正数任何子树的和都不可能等于整棵树的总和除非这棵树只有唯一一条路径且没有其他分支……其实也不成立。最稳妥的方法还是显式加入一个参数或者在主函数里记录root引用。还有一种更优雅的写法就是把计算子树和和收集候选乘积分开第一次遍历算总和第二次遍历单独处理每个非根节点。class Solution { long total 0; long ans 0; public int maxProduct(TreeNode root) { total sum(root); dfs(root); return (int)(ans % 1000000007); } private long sum(TreeNode node) { if (node null) return 0; return node.val sum(node.left) sum(node.right); } private long dfs(TreeNode node) { if (node null) return 0; long cur node.val dfs(node.left) dfs(node.right); ans Math.max(ans, cur * (total - cur)); return cur; } }等等这个写法也有问题。因为dfs在根节点处也会计算一次cur * (total - cur)而根节点此时cur等于total乘积是total * 0 0不影响最大值因为题目节点值都是正数其他切割位置的乘积肯定大于0。所以就算不排除根节点结果也不会错只不过多算了一个无意义的0而已。这算是一种无害的内部错误但不推荐因为如果哪天节点值出现负数或者零这个逻辑就会出问题。所以最终我实际采用的写法是在dfs里只计算非根节点的情况具体做法是传入一个布尔值或者把根节点单独特判一下。因为题目明确根节点没有父节点不存在切掉根节点上方的边这个操作在语义上就应该排除。顺便说一句树的递归遍历返回值设计很关键。这里dfs返回值必须是以当前节点为根的子树的节点和因为你要的是当前节点被切下来之后它所代表的整棵子树的和。如果返回值设计成到当前节点为止某条路径的和那这道题就完全做不出来了。这个设计直接决定后续的乘积公式能不能套用写代码之前一定先想清楚这个函数到底要返回什么语义。4. 完整可跑的写法与模运算的精度陷阱下面给出一版我最终提交通过、并且自认为注释足够清晰的完整解法。这版的变量命名、类型选择都经过斟酌照着抄也不会因为边界问题卡壳# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def maxProduct(self, root: Optional[TreeNode]) - int: MOD 10**9 7 # 第一趟计算整棵树的总和 def get_total(node): if not node: return 0 return node.val get_total(node.left) get_total(node.right) total get_total(root) self.best 0 # 第二趟DFS过程中收集每个非根子树的候选乘积 def dfs(node): if not node: return 0 left dfs(node.left) right dfs(node.right) cur_sum node.val left right # 只有非根节点才存在一条可以切断的、通向父节点的边 if node ! root: product cur_sum * (total - cur_sum) if product self.best: self.best product return cur_sum dfs(root) return self.best % MOD重点逐行解释一下关键位置get_total第一次递归必须完整跑完得到total。多花一次遍历是完全可以接受的因为总复杂度还是O(n)。dfs里面的left和right分别是左右子树的完整和再加上node.val得到当前整棵子树的和cur_sum。这里注意因为递归返回的是子树总和所以越往上的节点cur_sum就越大最大到根节点的total。product cur_sum * (total - cur_sum)这行是整个算法的灵魂。它把整棵树当前被切了一刀的结果用一个乘法表达了出来避免了删除边的模拟。为什么用if node ! root排除根节点因为根节点没有父节点不存在切掉它和父节点的边这个操作。如果你非要加上根节点算出来是total * 0 0不会影响当前的正数场景下的最大值但逻辑不干净给人感觉没想明白这题的本质。下面是我用Java再写一遍的版本主要是给习惯用Java刷题的朋友参考同时也演示一下long类型的使用class Solution { private long total; private long best; private TreeNode globalRoot; public int maxProduct(TreeNode root) { globalRoot root; total sum(root); best 0; traverse(root); return (int) (best % 1_000_000_007L); } private long sum(TreeNode node) { if (node null) return 0; return node.val sum(node.left) sum(node.right); } private long traverse(TreeNode node) { if (node null) return 0; long left traverse(node.left); long right traverse(node.right); long cur node.val left right; if (node ! globalRoot) { long product cur * (total - cur); if (product best) { best product; } } return cur; } }建议在本地跑一下这个测试用例直观感受分裂效果输入: [1,2,3,4,5,6] 1 / \ 2 3 / \ \ 4 5 6这棵树的总和是21。如果你切断2和1之间的边左子树和是11右边剩余是10乘积110。如果你切断3和1之间的边左子树和是9右边剩余是12乘积108。取最大值自然是110。跑一下代码确认输出110说明逻辑没问题。关于模运算这里我再展开说一次因为这道题在讨论区里吵了很久。由于我们要先比大小再返回取模结果所以比较阶段一定不能用模过的值。这也是为什么我前面强调要用原始乘积维护最大值。你可能会疑惑题目既然要求最终答案取模那我在比较过程中取模是不是也能过在绝大多数正数乘正数且目标是最小化/最大化的情况下用取模值比较几乎必然出错。举个例子两个候选乘积分别是1000000008和999999999真实情况下前者更大但前者对10^97取模等于1后者是999999999你如果拿取模后的值比较会觉得后者更大最终结果就错了。这类错误在模数恰好小于某个候选值时会暴露出来。凡是没有提前意识到这一点的解法都建议重新检查一遍。5. 这个解法的时间空间复杂度以及和同类型题目的横向对比算法复杂度这块必须专门说一下不仅因为面试会问也是因为写题时你自己心里要有数。整个算法做了两次递归遍历第一次递归sum每个节点访问一次时间复杂度O(n)。第二次递归traverse每个节点访问一次时间复杂度O(n)。合计时间复杂度O(n)n是节点个数。空间复杂度方面递归深度取决于树的高度。如果是完全二叉树递归深度是O(log n)如果是链状树每个节点只有左孩子或者只有右孩子递归深度是O(n)。所以最坏空间复杂度为O(n)。这个问题不少同学忽略了题目没有说这是平衡树所以按最坏情况分析递归栈可能很深。LeetCode的用例一般不会给到5万深的链状树否则Python很容易栈溢出但你不能假设所有平台都这么善良。再横向看看同类题目这道分裂二叉树的最大乘积和二叉树中的最大路径和有异曲同工之妙都是要在一次DFS过程中利用递归返回值携带以当前节点为根的子树信息然后在每个节点本地做一次候选答案的更新。区别在于最大路径和那一题递归返回的往往只是单边路径的最大贡献值而这一题返回的是整个子树的总和。理解了这两者的差异你等于同时掌握了两道高频树题的DFS设计思路。如果面试的时候碰到这题下面几个延伸问题也极有可能被追问提前想好答案很加分如果节点值可以为负数怎么办乘积还有可能是负数就不能再用0初始化best要初始化为Long.MIN_VALUE或者逻辑上允许比较出现负数。如果树非常大递归可能爆栈咋办可以改成迭代式后序遍历用栈模拟或者显式维护每个节点的后序访问顺序。为什么一定要先求total因为所有乘积的计算都依赖于total这个常量没有它就要被迫枚举每一条边再单独计算复杂度就退化成了O(n²)。6. 实战过程中我踩过的坑和总结的几条经验最后这部分是纯粹的经验分享写出来希望能帮你少走弯路。第一个坑直接用取模结果初始化best并参与比较。我第一版用Python写的时候习惯性地在每一次计算乘积后立刻取模然后和best比较提交后挂在一个比较大的测试用例上。排查了半天才发现是取模时机的问题。从那以后我形成一个习惯所有需要先比较大小再取模的题目中间计算一律用原始值取模只放在最后返回的时候做。第二个坑忘了节点值都是正数这个条件其实是个便利条件。当我知道了所有节点值都是正数时我可以放心地用0初始化best因为任何一条边切出来的两个子树和都大于0乘积也大于0。如果节点值可能出现负数0作为初始值就可能漏掉负数的正确答案。题目里明确写了节点值范围是1到10000属于正向提示不要忽略这种细节。第三个坑在检查是否该跳过根节点时我一开始写的是if (cur ! total)想当然认为子树和等于total的节点就是根节点。但仔细一想如果整棵树只有一个节点那么根节点的子树和就是total此时确实满足cur total但这个写法在特殊形态的树上可能出错吗节点值都是正数时任意非根子树的节点集合一定不包含整棵树的所有节点所以其和必然小于total。这么看似乎可以用cur ! total来判断。但这么写终究不直观而且把判断条件建立在节点值全部为正数这个前提上不够健壮。用node ! root最直白逻辑上无懈可击。此外我还想分享一个日常刷题的小习惯当一道树的题需要切割/分裂/删除边时先想一想能不能通过子树和来表达结果而不是真的去修改树结构。这个思路在二叉树题目里出现频率极高比如删除子树和为某个值的子树、判断能否通过删除一条边使得两棵树相等等等本质上都用到了同一招——后序遍历返回子树信息在上层做判断。这题做顺手之后我又把最早写的暴力枚举版本翻出来做了个对比测试用一个随机的5万节点二叉树测试暴力版本跑了大概两三秒而两次DFS的版本只跑了不到50毫秒。刷题这种场景时间差距直接决定你能不能AC。最后给一个刷题顺序建议这题非常适合和有类似结构的二叉树最大路径和组合起来练习一天一道连着两天刷完你对子树信息这个概念的理解会明显上一个台阶。刷的时候记得故意写一版取模时机错误的代码再把它修好这个过程比自己看十遍别人的正确代码都有用。
