LeetCode 题解工作台
统计最高分的节点数目
给你一棵根节点为 0 的 二叉树 ，它总共有 n 个节点，节点编号为 0 到 n - 1 。同时给你一个下标从 0 开始的整数数组 parents 表示这棵树，其中 parents[i] 是节点 i 的父节点。由于节点 0 是根，所以 parents[0] == -1 。 一个子树的 大小 为这个子…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们先根据给定的父节点数组 `parents` 构建图 ，其中 表示节点 的所有子节点。定义变量 表示最高得分的节点数目，变量 表示最高得分。 然后，我们设计一个函数 $dfs(i, fa)$，它的作用是计算节点 的分数，并返回以节点 为根的子树的节点数目。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵根节点为 0 的 二叉树 ，它总共有 n 个节点，节点编号为 0 到 n - 1 。同时给你一个下标从 0 开始的整数数组 parents 表示这棵树，其中 parents[i] 是节点 i 的父节点。由于节点 0 是根，所以 parents[0] == -1 。
一个子树的 大小 为这个子树内节点的数目。每个节点都有一个与之关联的 分数 。求出某个节点分数的方法是，将这个节点和与它相连的边全部 删除 ，剩余部分是若干个 非空 子树，这个节点的 分数 为所有这些子树 大小的乘积 。
请你返回有 最高得分 节点的 数目 。
示例 1:
输入：parents = [-1,2,0,2,0] 输出：3 解释： - 节点 0 的分数为：3 * 1 = 3 - 节点 1 的分数为：4 = 4 - 节点 2 的分数为：1 * 1 * 2 = 2 - 节点 3 的分数为：4 = 4 - 节点 4 的分数为：4 = 4 最高得分为 4 ，有三个节点得分为 4 （分别是节点 1，3 和 4 ）。
示例 2：
输入：parents = [-1,2,0] 输出：2 解释： - 节点 0 的分数为：2 = 2 - 节点 1 的分数为：2 = 2 - 节点 2 的分数为：1 * 1 = 1 最高分数为 2 ，有两个节点分数为 2 （分别为节点 0 和 1 ）。
提示：
n == parents.length2 <= n <= 105parents[0] == -1- 对于
i != 0，有0 <= parents[i] <= n - 1 parents表示一棵二叉树。
解题思路
方法一：DFS
我们先根据给定的父节点数组 parents 构建图 ，其中 表示节点 的所有子节点。定义变量 表示最高得分的节点数目，变量 表示最高得分。
然后，我们设计一个函数 ，它的作用是计算节点 的分数，并返回以节点 为根的子树的节点数目。
函数 的计算过程如下：
我们首先初始化变量 ，表示以节点 为根的子树的节点数目；变量 ，表示以节点 初始分数。
接下来，我们遍历节点 的所有子节点 ，如果 不是节点 的父节点 ，那么我们递归调用 ，并将返回值累乘到 中，同时将返回值累加到 中。
遍历完子节点后，如果 ，那么我们将 累乘到 中。
然后，我们判断 是否小于 ，如果小于，那么我们将 更新为 ，并将 更新为 ；如果等于，那么我们将 更新为 。
最后，我们返回 。
最终，我们调用 ，并返回 。
时间复杂度 ，空间复杂度 。其中 是节点数目。
class Solution:
def countHighestScoreNodes(self, parents: List[int]) -> int:
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
A candidate who correctly identifies the need for DFS traversal and state tracking will perform well.
- question_mark
Candidates should be comfortable with tree traversal and recognizing the implications of removing nodes in terms of subtree sizes.
- question_mark
Look for clarity in how candidates compute the scores and handle edge cases, particularly the root node.
常见陷阱
外企场景- error
Failing to correctly compute the subtree sizes, especially for the root node or leaf nodes.
- error
Not handling cases where the node has no children or only one child correctly, leading to inaccurate score calculations.
- error
Overcomplicating the solution or missing the need for DFS traversal to efficiently calculate subtree sizes.
进阶变体
外企场景- arrow_right_alt
Change the tree structure to allow more than two children per node, which will require adjusting the approach for calculating subtree sizes.
- arrow_right_alt
Introduce constraints where some nodes can be removed but not others, changing the calculation of scores based on node removal eligibility.
- arrow_right_alt
Modify the problem to consider multiple trees (forest) and determine the highest score across all trees combined.