LeetCode 1339《分裂二叉树的最大乘积》这题名字听着挺唬人拆开看其实就两件事把一棵二叉树删一条边切成两半再让两半节点值之和的乘积最大。我第一次做它是在每日一题打卡时前十分钟觉得简单后十分钟才发现坑一个接一个——取模时机、递归深度、候选值边界随便踩一个都让人抓狂。这篇文章就把我的完整思路、可直接运行的代码、还有那些搜索引擎里不会写清楚的小细节一次性讲完适合正在刷二叉树、准备面试、或者单纯想弄清楚最大乘积到底怎么算的读者。1. 拆题分裂一棵二叉树先把它变成一道数学题1.1 题目到底让你做什么题目原文很长核心就一句话给定一棵二叉树删除一条边把它分成两棵非空子树然后计算两棵子树各自节点值之和的乘积返回最大乘积对 10^9 7 取模的结果。这里有个很容易被忽略的隐藏条件节点值是非负整数树的总节点数最多 10^4。我刷题时第一反应是那我把每一条边都剪一下试试看但仔细一想剪掉一条边后整个树被分成两部分一边是某个子树被剪下来的树另一边是整棵树减去这个子树的部分。也就是说分裂结果完全由你剪下来的那棵子树决定。设整棵树的节点值总和为total。剪下某个子树后该子树的和为x剩下的部分自然是total - x。我们要最大化的就是x * (total - x)这样一来题目从在一棵树上删边变成了找到一个合法的子树和 x让这个乘积最大。1.2 最接近总和一半的候选乘积最大为什么找一个合适的 x 就够了因为上面的式子是一个关于 x 的二次函数展开是f(x) -x^2 total * x这个函数开口向下对称轴在x total / 2处。二次函数的性质是离对称轴越近函数值越大。所以我们要找的就是所有合法候选 x 中最接近total / 2的那一个。为了直观我列了一个 total 100 的表格子树和 x另一部分 total - x乘积4951249950502500406024002080160080201600可以看出越接近 50乘积越大。极端一点如果某个分裂点子树和是 1乘积只有 99而 49 和 51 的分裂乘积接近 2500差距是数量级的。所以整个题的核心变成了把所有合法的子树和都找出来挑一个最接近total / 2的。1.3 total 本身不是合法候选这里有个我实战中踩过的边界坑total这个值本身能不能放进候选集合答案是不能。如果你把total放进候选另一部分就是total - total 0乘积是 0。但仔细想删除一条边后两棵子树都必须非空你不可能把整棵树原封不动地当作剪下来的那一半剩下的部分是空树。这在二叉树的定义里不构成合法的分裂。那怎么避免这个问题常见做法是在递归求子树和的过程中只把非根节点对应的子树和加入候选列表。因为只有非根节点作为被剪下子树的根时才存在一条真实的边可以剪。根节点对应整棵树没有一条边能把整棵树从树里剪下来。注意如果题目测试数据给了一棵只有一个节点的树那按道理没有边可删这类题通常不会出现这种用例。但代码里最好还是用node is not root的方式排除根节点逻辑更严谨。2. 一次后序遍历拿全所有候选分裂点2.1 为什么要用后序遍历求以某个节点为根的子树的节点值之和这是典型的后序遍历场景。后序遍历的顺序是左子树、右子树、根节点它天然保证在计算某个节点的时候它的左右子树已经算完了。你只要把左右子树的返回值加起来再加上自己的node.val就能得到当前子树的和。如果你用前序或中序遍历也能写但需要一个额外的栈或反向累加容器逻辑反而绕。后序是这道题最自然、最不容易出错的做法。我第一次写时用的是递归版后序代码清爽思路明确。但后来测试一个链状树时差点因为递归深度爆栈挂了所以下面第 3 章我会专门说这个问题。2.2 Python 参考实现下面是可直接运行的完整解法class Solution: def maxProduct(self, root: Optional[TreeNode]) - int: MOD 10**9 7 candidates [] def dfs(node: Optional[TreeNode]) - int: if node is None: return 0 left_sum dfs(node.left) right_sum dfs(node.right) cur left_sum right_sum node.val # 根节点的 cur 就是 total不是合法分裂点跳过 if node is not root: candidates.append(cur) return cur total dfs(root) best 0 for s in candidates: if abs(2 * s - total) abs(2 * best - total): best s return (best * (total - best)) % MOD核心逻辑就三步dfs递归求子树和同时把所有非根节点的子树和存进candidates。遍历candidates用abs(2 * s - total)找到最接近total / 2的值。用找到的best计算乘积并取模返回。为什么用2 * s - total而不是s - total / 2因为前者全是整数运算避免了浮点数比较带来的精度问题速度也更快。这个技巧在后面第 4 章还会提到。2.3 时间复杂度和空间占用时间复杂度是 O(N)每个节点只访问一次。空间复杂度由两部分组成递归栈最深能达到树的高度 H最坏情况下 H Ncandidates列表最多存 N 个值所以整体空间是 O(N)。对于 10^4 量级的节点数这个开销完全可接受。不过这里有个细节值得说如果你用的是递归写法那么树的高度直接决定了递归栈深度。对于像链式二叉树这种退化结构树深就是 N达 10000 层。Python 默认递归深度限制是 1000所以你如果直接把上面的代码丢进本地环境跑链状树大概率会收到一个RecursionError。这就是很多人吐槽写二叉树程序时为什么总是报运行时错误的主要原因之一。3. 写二叉树程序时为什么总是报运行时错误这个问题我在群里见过无数次也在周赛里吃过亏。结合 1339 这道题常见的运行时错误主要有三类我一个个说。3.1 最常见的原因递归深度超过默认限制前面说了Python 默认递归深度约 1000。LeetCode 这题节点数最多 10^4如果树的形态退化成一条链深度就是 10000。在这种情况下任何递归后序遍历都会直接爆掉报RecursionError: maximum recursion depth exceeded。解决办法有两个。第一个很简单在代码开头调大递归限制import sys sys.setrecursionlimit(20000)但要注意setrecursionlimit只是放宽了上限真正的物理限制是 C 调用栈设得太大可能导致程序崩溃一般设到 20000 就够这类题用了。第二个办法是改成迭代式后序遍历。这里教大家一个很实用的技巧先用一个栈做先序遍历记录访问顺序然后逆序累加子树和。因为先序遍历的顺序里父节点永远比子节点先被记录逆序处理时子节点一定先于父节点被计算正好等价于后序求子树和。def iterative_postorder_sums(root): stack [root] order [] while stack: node stack.pop() if node is None: continue order.append(node) stack.append(node.left) stack.append(node.right) sub_sum {} for node in reversed(order): left sub_sum.get(node.left, 0) right sub_sum.get(node.right, 0) sub_sum[node] left right node.val return sub_sum这个写法不受递归深度限制代码量也不大可以作为递归版的一个备选方案。面试时先写递归再提一句如果想完全避免递归爆栈我可以用迭代版会显得经验很足。我把常见错误和解决手段整理成了表格方便自查错误类型触发场景解决手段RecursionError树深度超过递归限制调大 recursionlimit 或改迭代AttributeError: NoneType未判空就访问node.left每个节点使用前先判断是否为 None答案错误WA把 total 当候选值、取模时机不对排除根节点、最后统一取模3.2 空指针和判空二叉树的基本素养很多二叉树崩溃是空指针访问导致的。题目给的树不一定是完全二叉树某个节点可能只有左孩子没有右孩子可能两个都没有。你在递归里如果不写if node is None: return 0那么当 node 是 None 时访问node.left或node.val就会直接报错。这几乎是所有二叉树题目的通用前提1339 也不例外。尤其注意迭代版的顺序处理里栈中可能出现 None用continue跳过是标准做法。总之写树相关代码时判空不是可选项而是必选项。3.3 别把普通二叉树当搜索二叉树热搜词里有个搜索二叉树我估计不少人是在看二叉树题时被这个概念带偏了。需要明确LeetCode 1339 的输入是普通二叉树不是二叉搜索树。普通二叉树没有任何有序性节点值大小关系和位置无关。如果你试图用 BST 的思路去想问题比如中序遍历有序、找某个区间、用 lower_bound 优化在这题里完全用不上。我见过有人把这道题往搜索二叉树上靠推导了半天子树和是否满足单调性最后发现是死路。这题的候选是所有子树和顺序和 BST 没有任何关系。正确姿势就是老老实实做后序遍历求和别被带偏。4. 模运算与溢出两个在周赛里炸掉无数人的细节4.1 取模不能参与最大值比较题目要求返回最大乘积对 10^9 7 取模。很多新手包括我早期会写出这样的代码ans max(ans, (s * (total - s)) % MOD)然后一脸困惑地发现答案偶尔不对。原因很简单取模不是保序操作。两个数取模之后的大小关系和取模之前的大小关系不一定一致。你不能用% MOD之后的结果来判断哪个真实乘积更大。正确做法是在寻找best的过程中全程使用真实整型乘积做比较只在最终返回时取模。因为我们这道题数据范围下最大乘积约为(5e7)^2 2.5e15这个数字在现代编程语言的 64 位整型里完全放得下所以不需要担心比较真实值会溢出。对应到代码正确写法是ans max(ans, s * (total - s)) return ans % MOD4.2 语言差异int 溢出是 C/Java 的特产Python 的整数是任意精度的所以我上面的 Python 代码不需要考虑溢出问题。但如果你用 C 或 Java 提交就有一个非常隐蔽的坑s和total - s如果都是int那s * (total - s)这个乘法是在 int 范围内进行的结果一旦超过 2^31 - 1约 21 亿就会溢出成负数赋给 long long 也已经晚了。比如total最大是10^8两个5e7相乘等于2.5e15远超 int 上限。所以 C 里至少要把一个操作数转成 long longlong long product 1LL * s * (total - s);Java 同理用long类型。这里我把各个语言的注意事项列个表语言数值类型是否安全Pythonint任意精度安全无需处理Clong long安全乘法前转 long longJavalong安全用 long 接收C/Java 的 int4 字节不安全乘积会溢出4.3 比较最接近值时用 2 倍而不是浮点我在第 2 章提到用abs(2 * s - total)找最接近值原因再展开说一下。如果用abs(s - total / 2.0)你会在代码里引入浮点数。浮点比较在边界场景可能产生误差而且没必要。把两边都乘以 2相当于比较|2s - total|全部由整数运算完成又准又快。这个技巧在处理找最接近一半的题目里非常通用不只是 1339很多平均分配类问题都可以这样用。5. 如果面试官让你压缩空间线索二叉树与两趟遍历5.1 Morris 遍历线索化思想的适用边界热搜词里有线索二叉树这个恰好和 1339 的进阶优化有关。线索二叉树的核心思想是利用节点空闲的left/right指针临时保存遍历时需要回退的信息从而把遍历的空间复杂度从 O(H) 降到 O(1)。Morris 遍历就是在线索化思想上的经典实现——它不用栈也不用递归而是在遍历过程中把树临时改造成带线索的结构访问完后再恢复原状。Morris 中序遍历相对简单前序也还行但后序 Morris 是三者中最麻烦的。因为后序要求先左、再右、最后根用线索回退时无法像中序那样自然地回到根需要额外处理右边界和反转逻辑。你让我在面试现场手写后序 Morris我是会犹豫的——不是不会而是容易在细节上翻车。所以我的建议是除非面试官明确要求 O(1) 空间否则不要主动选择 Morris。你可以把它作为一个加分项提出来但第一版代码还是用递归后序。这样既能保证正确率又展示了你的知识面。5.2 不存列表的两趟后序遍历如果你不追求 O(1)但又想省掉candidates列表可以换成两趟遍历第一趟后序遍历只求整棵树的total。第二趟后序遍历每计算出一个非根节点的子树和cur就直接用它和total更新best不需要存储任何列表。这样空间从 O(N) 降到 O(H)代价是遍历了两遍时间从 O(N) 变成 O(2N)常数变大但复杂度没变。面试时这是一个不错的中间优化方案。第二趟的代码核心是这样best [0] def dfs2(node: Optional[TreeNode]) - int: if node is None: return 0 left dfs2(node.left) right dfs2(node.right) cur left right node.val if node is not root and abs(2 * cur - total) abs(2 * best[0] - total): best[0] cur return cur这里用best[0]而不是best是为了在 Python 的内部函数里方便修改外层变量。如果你用nonlocal也行面试时解释清楚即可。5.3 我的个人取舍与刷题体会我把三种方案的取舍用一段话总结给自己备忘也分享给你如果是日常刷题或比赛直接用递归后序 candidates列表最清晰不容易错。如果担心递归深度就用迭代先序 反向累加。如果面试官追问空间优化先说两趟遍历再说可以上 Morris 后序但不要主动把自己写晕。我个人实际刷这题的体会是LeetCode 1339 真正的考点不是难而是细。它把二叉树遍历、数学建模、取模边界三个点放在同一道题里任何一个环节想当然都会挂。如果你也经常因为运行时错误被卡不妨从递归深度和类型溢出这两个方向先自查。刷题就像解谜每次踩坑后把原因记下来下一次遇到类似的树形 DP 题就能少走很多弯路。