题目描述
思路解析动画文字版
记牢这一句:分数等于删掉该节点后各块大小的乘积。块分两种,一种是它的每棵子树,大小直接是子树 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题