题目描述
思路解析
一句话答案：LeetCode 2049 统计最高分的节点数目：删一个节点后树裂成各棵子树加上方一块，分数是各块大小连乘；一趟后序 DFS 求出所有子树大小顺带算分，时间 O(n)。
题给的是 parents 数组，分数最高的节点有几个
树不是直接给左右孩子，而是给一个 parents 数组：parents[i] 是节点 i 的父亲，根节点 0 的父亲记为 -1。一个节点的分数这么算：把它和连着的边全删掉，树散成几块非空的连通部分，分数就是这几块大小的乘积。要返回分数最高的节点一共有几个。题面例子 parents=[-1,2,0,2,0] 有 5 个节点，答案是 3。
对每个节点单独删边、数连通块，慢在哪
按定义走，就得对每个节点都来一次：删掉它、在剩下的图里数出每一块多大、再连乘。可这样删一个节点就要把整棵树重走一遍，n 个节点走 n 遍，总量到了 O(n²)。节点数能到十万，平方级要上百亿次操作，直接超时。
删一个节点，树到底裂成哪几块
删掉节点 i，它的每棵子树各自成一块，大小就是那棵子树的节点数；剩下它的父亲、祖先和旁系分支连成另一整块，大小是 n 减去 i 的子树大小。所以一个节点的分数只取决于两样：它每棵子树的大小，和 n 减自己的子树大小。而所有子树大小，只要从叶子朝根走一趟就能全部求出：每到一个节点，它底下几棵子树的大小都已经先算好、递上来了，这种走法就是后序遍历。
一趟 DFS 里，每个节点返回什么、乘什么
先把 parents 转成孩子表，也就是每个节点记下它有哪些孩子，方便往下走。然后一趟 DFS，让它返回以当前节点为根的子树大小 cnt。在每个节点上，cnt 和 score 都从 1 起；遍历它的每个孩子，拿到孩子返回的子树大小 t，就把 t 乘进 score、把 t 加进 cnt。孩子都处理完，若 n 减 cnt 大于 0，再把这块上方块乘进 score。这时 score 就是删掉该节点的分数，拿它和当前最高分比：更大就刷新最高分、把计数重置成 1，相等就计数加一。
拿 parents=[-1,2,0,2,0] 把五个节点算一遍
这棵树里节点 0 是根，孩子是 2 和 4；节点 2 挂着 1 和 3；节点 1、3、4 都是叶子。先求子树大小：三个叶子各是 1，节点 2 是 1+1+1=3，节点 0 是 1+3+1=5。再逐个删：节点 0 的上方块 5-5=0 跳过，分数 3×1=3；节点 1 是叶子，上方块 5-1=4，分数 4；节点 2 两棵子树各 1、上方块 5-3=2，分数 1×1×2=2；节点 3、节点 4 也是叶子，分数各 4。最高分是 4，节点 1、3、4 三个达到，答案 3。
一趟 O(n) 就够，难的是别让分数悄悄算歪
建孩子表扫一遍 parents 是 O(n)，一趟 DFS 每个节点只访问一次、只做常数次运算，合起来时间 O(n)；孩子表加最坏退化成链时的递归栈，空间 O(n)。分数是几块大小连乘，接近均分时最坏到 1e13 量级，int 存会溢出，C++ 用 long long、Java 用 long，Python 整数无上限不用管。真正让分数悄悄算歪的都在收尾几笔：上方那块要是漏乘，分数就偏小；根节点压根没有上方块，得先判 n 减子树大小大于 0，否则乘个 0 就把分数归零；碰到更高的分数，计数要记得从 1 重开，忘了重置就会多算。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:分数等于删掉该节点后各块大小的乘积。块分两种,一种是它的每棵子树,大小直接是子树 size;另一种是上方剩下的那块,大小是 n 减去它的子树大小。下面先把五个节点的子树大小求出来。
总览 · 5 个节点的二叉树：这就是要处理的树。节点 0 是根,它有两个孩子节点 2 和节点 4;节点 2 底下又挂着节点 1 和节点 3;节点 4、节点 1、节点 3 都是叶子。一共 5 个节点。第一步不急着算分,先自底向上把每个节点的子树大小求出来,后面算分全靠它。
子树大小 · 节点 1 = 1：先看最底下的叶子节点 1。它没有孩子,子树里就它自己一个,子树大小是 1。叶子的子树大小永远是 1,这是递归的底。
子树大小 · 节点 3 = 1：同样,叶子节点 3 也没有孩子,子树大小是 1。它和节点 1 是节点 2 的两个孩子。
子树大小 · 节点 2 = 3：轮到节点 2。它的子树包含它自己,加上左孩子节点 1 的子树 1 个、右孩子节点 3 的子树 1 个,所以子树大小是 1 加 1 加 1,等于 3。这三个绿色节点就是节点 2 那一整棵子树。
子树大小 · 节点 4 = 1：再看叶子节点 4,它挂在根节点 0 下面,没有孩子,子树大小是 1。
子树大小 · 节点 0 = 5：最后是根节点 0。它的子树就是整棵树,自己 1 个,加上节点 2 那棵 3 个、节点 4 那棵 1 个,子树大小是 1 加 3 加 1,等于 5,正好是全部节点数。
子树大小全部到手：五个节点的子树大小都到手了:节点 0 是 5,节点 2 是 3,节点 1、节点 3、节点 4 各是 1。有了这张表,接下来就能一个一个删节点、算分数。约定好评分口径:删掉节点后剩下的每一块大小相乘。下面按节点编号 0 到 4 的顺序逐个算。
删掉根节点 0 · 分成两棵子树：第一个算根节点 0。把节点 0 和它的两条边删掉,树就断成两块,正好是它的两棵子树:节点 2 领头那棵 3 个节点,节点 4 单独那棵 1 个节点。根节点比较特殊,它上面没有别的节点,所以没有上方那一块,下一帧确认一下。
节点 0 结算 · 分数 = 3：节点 0 的分数就是两棵子树大小相乘:3 乘 1 等于 3。它是第一个算的,先把当前最高分记成 3,达到最高分的节点数记成 1。别急着下结论,后面还有四个节点。
删掉叶子节点 1 · 只裂出一块：轮到叶子节点 1。它没有孩子,删掉它以后,剩下的 4 个节点还连成一整块,不会散开。所以只裂出上方这一块,大小下一帧算。
节点 1 的上方块 · 大小 = 4：再看上方那一块。它等于总数 n 减去节点 1 的子树大小,也就是 5 减 1 等于 4。这 4 个节点是删点之后除它子树以外剩下的全部,连在一起算一块。叶子就这一块。
节点 1 结算 · 分数 = 4：节点 1 的分数是各块大小相乘:4 = 4。这个 4 比之前的最高分 3 还大,所以刷新最高分为 4,并把达到最高分的节点数重新记成 1。注意叶子删完只剩一块,分数就等于那块的大小 4。
删掉节点 2 · 先看两棵子树：轮到节点 2。删掉它和连着的边,先看它自己的子树:左孩子节点 1 那棵大小 1,右孩子节点 3 那棵大小 1。除了这两棵,它上面还连着一块,下一帧单独算。
节点 2 的上方块 · 大小 = 2：再看上方那一块。它等于总数 n 减去节点 2 的子树大小,也就是 5 减 3 等于 2。这 2 个节点是删点之后除它子树以外剩下的全部,连在一起算一块。加上前面两棵子树,节点 2 删完一共 3 块。
节点 2 结算 · 分数 = 2：节点 2 的分数是 1 × 1 × 2 = 2。它比当前最高分 4 小,不是我们要的,最高分和计数都保持不变。可以看到节点 2 虽然裂成三块,乘积却只有 2,反而不占优。
删掉叶子节点 3 · 只裂出一块：轮到叶子节点 3。它没有孩子,删掉它以后,剩下的 4 个节点还连成一整块,不会散开。所以只裂出上方这一块,大小下一帧算。
节点 3 的上方块 · 大小 = 4：再看上方那一块。它等于总数 n 减去节点 3 的子树大小,也就是 5 减 1 等于 4。这 4 个节点是删点之后除它子树以外剩下的全部,连在一起算一块。叶子就这一块。
节点 3 结算 · 分数 = 4：节点 3 的分数是 4 = 4。它正好等于当前最高分 4,不刷新最高分,但达到最高分的节点数加一,变成 2。又一个叶子拿到 4 分。
删掉叶子节点 4 · 只裂出一块：轮到叶子节点 4。它没有孩子,删掉它以后,剩下的 4 个节点还连成一整块,不会散开。所以只裂出上方这一块,大小下一帧算。
节点 4 的上方块 · 大小 = 4：再看上方那一块。它等于总数 n 减去节点 4 的子树大小,也就是 5 减 1 等于 4。这 4 个节点是删点之后除它子树以外剩下的全部,连在一起算一块。叶子就这一块。
节点 4 结算 · 分数 = 4：节点 4 的分数是 4 = 4。它正好等于当前最高分 4,不刷新最高分,但达到最高分的节点数加一,变成 3。又一个叶子拿到 4 分。
叶子的规律 · 分数都是 n 减 1：停下来看个规律。三个叶子节点 1、3、4 的分数都是 4,也就是 n 减 1。原因很直接:删掉一个叶子,剩下的节点全都还连成一整块,大小就是 n 减 1,而这块又是唯一一块,乘积就是它自己。所以在很多树里,叶子的分数天然不低,常常就是那个最高分。
回放 · 最高分 4,三个节点达到,答案 3：五个节点全算完了。分数依次是节点 0 得 3、节点 1 得 4、节点 2 得 2、节点 3 得 4、节点 4 得 4。最高分是 4,达到它的有节点 1、节点 3、节点 4 三个,所以答案是 3。整个过程就是一趟后序求子树大小,再对每个节点把各块大小相乘比一比,时间是线性的。
边界想清:两节点都得 1、星形树两叶子并列最高、链形树两端并列最高,都可能出现多个节点同分。
面试重点:分数只依赖子树大小故一趟 DFS 搞定、乘积会溢出要用 long、上方块是删点后除子树外的剩余连通块。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *import sysclass TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def countHighestScoreNodes(self, parents: List[int]) -> int: # 链形树递归深度可达 n(最多十万),先调高递归上限,避免 RecursionError sys.setrecursionlimit(200005) def dfs(i: int, fa: int): cnt = score = 1 for j in g[i]: if j != fa: t = dfs(j, i) score *= t cnt += t if n - cnt: score *= n - cnt nonlocal ans, mx if mx < score: mx = score ans = 1 elif mx == score: ans += 1 return cnt n = len(parents) g = [[] for _ in range(n)] for i in range(1, n): g[parents[i]].append(i) ans = mx = 0 dfs(0, -1) return ans复杂度
- 时间：O(n)，建孩子表扫一遍 parents 是 O(n);一趟 DFS 每个节点恰好访问一次,每次只做常数次乘法和比较。合起来随节点数线性增长
- 空间：O(n)，按峰值算。孩子表 g 存 n 减 1 条边,是 O(n);递归栈深度最坏是树退化成一条链时的 O(n)。两者都是 O(n),不额外开更大的表
易错点
面试追问把动画讲成自己的话
追问为什么一趟 DFS 就够,不用对每个节点单独重算?
追问分数会不会溢出,怎么处理?
追问上方那一块到底指什么?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
从一个节点到另一个节点每一步的方向
LeetCode 2096 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题