题目描述
思路解析动画文字版
记住「先求各子树和与 total,再枚举砍边算 sub ×(total − sub) 取最大,最后才取模」,下面逐帧套它。
阶段一 · 求各子树和：第一步:后序遍历,先算孩子、再算自己,求出每个节点的子树和。后序保证算到某个节点时,它的左右子树和都已就绪。
到达 50：走到节点 50(紫色),先把它的孩子都算完,再回头算它自己的子树和。
到达 30：走到节点 30(紫色),先把它的孩子都算完,再回头算它自己的子树和。
到达 10：走到节点 10(紫色),它是叶子,子树里只有它自己。
算出 10 的子树和：节点 10 的子树和 = 10 = 10(变绿,存进列表)。
到达 40：走到节点 40(紫色),它是叶子,子树里只有它自己。
算出 40 的子树和：节点 40 的子树和 = 40 = 40(变绿,存进列表)。
算出 30 的子树和：节点 30 的子树和 = 30 + 10 + 40 = 80(变绿,存进列表)。
到达 80：走到节点 80(紫色),先把它的孩子都算完,再回头算它自己的子树和。
到达 60：走到节点 60(紫色),它是叶子,子树里只有它自己。
算出 60 的子树和：节点 60 的子树和 = 60 = 60(变绿,存进列表)。
算出 80 的子树和：节点 80 的子树和 = 80 + 60 = 140(变绿,存进列表)。
算出 50 的子树和：节点 50 的子树和 = 50 + 80 + 140 = 270(变绿,存进列表)。它是根,这个和就是整棵树的总和 total。
总和就绪：所有子树和都算出来了,根的子树和 270 就是总和 total。接下来枚举每一棵子树:砍掉它上面那条边,看 sub ×(total − sub) 有多大。
砍 10 上面的边：砍掉节点 10 上面那条边:红色这棵子树和 = 10,蓝色剩下那半 = 270 − 10 = 260,乘积 = 2600。比之前大,刷新 best = 2600。
砍 40 上面的边：砍掉节点 40 上面那条边:红色这棵子树和 = 40,蓝色剩下那半 = 270 − 40 = 230,乘积 = 9200。比之前大,刷新 best = 9200。
砍 30 上面的边：砍掉节点 30 上面那条边:红色这棵子树和 = 80,蓝色剩下那半 = 270 − 80 = 190,乘积 = 15200。比之前大,刷新 best = 15200。
砍 60 上面的边：砍掉节点 60 上面那条边:红色这棵子树和 = 60,蓝色剩下那半 = 270 − 60 = 210,乘积 = 12600。没超过当前 best = 15200,保持不变。
砍 80 上面的边：砍掉节点 80 上面那条边:红色这棵子树和 = 140,蓝色剩下那半 = 270 − 140 = 130,乘积 = 18200。比之前大,刷新 best = 18200。
根上面没有边：代码里会把根的子树和 270 也算进去,但 270 ×(270 − 270)= 270 × 0 = 0,等于没切,自然不会被选为最大,可以放心一起遍历。
最优砍法：所有砍法里,砍 80 上面那条边最优:把树分成和为 140 和 130 的两半,两者最接近一半,乘积最大 = 18200。
最后取模：最后一步才对最大乘积取模:18200 % (1e9+7) = 18200(本例数不大,取模后不变)。注意取模一定放在取完最大值之后,要是一边算乘积一边取模、再拿取模后的值比大小,就会比错。
边界:两节点就一条边;链也按 sub×(total−sub) 试;大数最后取模。
面试重点:total 必须先拿到才能算乘积,树可只遍历一遍(收集子树和加得 total)再扫列表;乘积在两半相等时最大(抛物线)。
参考代码
from typing import List, Optionalclass TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def maxProduct(self, root: Optional[TreeNode]) -> int: sums = [] def dfs(node): if not node: return 0 s = node.val + dfs(node.left) + dfs(node.right) sums.append(s) return s total = dfs(root) return max(s * (total - s) for s in sums) % (10**9 + 7)复杂度
- 时间：O(n)，一遍后序 DFS 求所有子树和 O(n);再遍历 n 个子树和算乘积 O(n);n 是节点数
- 空间：O(n)，存所有子树和的列表 O(n),外加递归栈 O(h);最坏 O(n)
易错点
面试追问把动画讲成自己的话
追问能不能不做第二次树遍历,少扫一遍树?
追问为什么乘积最大时两棵子树的和会尽量接近?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉树中的最长交错路径
LeetCode 1372 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题