LeetCode 题解工作台
统计好节点的数目
现有一棵 无向 树，树中包含 n 个节点，按从 0 到 n - 1 标记。树的根节点是节点 0 。给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [a i , b i ] 表示树中节点 a i 与节点 b i 之间存在一条边。 如果一个节点的所有子节点为根的 子…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们先根据题目给定的边 构建出树的邻接表 ，其中 表示节点 的所有邻居节点。 然后，我们设计一个函数 $\textit{dfs}(a, \textit{fa})$，表示计算以节点 为根的子树中的节点数，并累计好节点的数量。其中 表示节点 的父节点。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
现有一棵 无向 树，树中包含 n 个节点，按从 0 到 n - 1 标记。树的根节点是节点 0 。给你一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ai, bi] 表示树中节点 ai 与节点 bi 之间存在一条边。
如果一个节点的所有子节点为根的 子树 包含的节点数相同，则认为该节点是一个 好节点。
返回给定树中 好节点 的数量。
子树 指的是一个节点以及它所有后代节点构成的一棵树。
示例 1：
输入：edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
输出：7
说明：
树的所有节点都是好节点。
示例 2：
输入：edges = [[0,1],[1,2],[2,3],[3,4],[0,5],[1,6],[2,7],[3,8]]
输出：6
说明：
树中有 6 个好节点。上图中已将这些节点着色。
示例 3：
输入：edges = [[0,1],[1,2],[1,3],[1,4],[0,5],[5,6],[6,7],[7,8],[0,9],[9,10],[9,12],[10,11]]
输出：12
解释：
除了节点 9 以外其他所有节点都是好节点。
提示：
2 <= n <= 105edges.length == n - 1edges[i].length == 20 <= ai, bi < n- 输入确保
edges总表示一棵有效的树。
解题思路
方法一：DFS
我们先根据题目给定的边 构建出树的邻接表 ，其中 表示节点 的所有邻居节点。
然后，我们设计一个函数 ，表示计算以节点 为根的子树中的节点数，并累计好节点的数量。其中 表示节点 的父节点。
函数 的执行过程如下：
- 初始化变量 , , ，分别表示节点 的某个子树的节点数、节点 的所有子树的节点数、以及节点 是否为好节点。
- 遍历节点 的所有邻居节点 ，如果 不等于 ，则递归调用 ，返回值为 ，并累加到 中。如果 ，则将 赋值给 ；否则，如果 不等于 ，说明节点 的不同子树的节点数不同，将 置为 。
- 最后，累加 到答案中，并返回 。
在主函数中，我们调用 ，最后返回答案。
时间复杂度 ，空间复杂度 。其中 表示节点的数量。
class Solution:
def countGoodNodes(self, edges: List[List[int]]) -> int:
def dfs(a: int, fa: int) -> int:
pre = -1
cnt = ok = 1
for b in g[a]:
if b != fa:
cur = dfs(b, a)
cnt += cur
if pre < 0:
pre = cur
elif pre != cur:
ok = 0
nonlocal ans
ans += ok
return cnt
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
g[b].append(a)
ans = 0
dfs(0, -1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each node is visited once during DFS. Space complexity is O(n) for the adjacency list and recursion stack in the worst case, depending on the tree depth. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Emphasizes DFS recursion and state tracking.
- question_mark
Expects handling of edge cases where nodes have varying numbers of children.
- question_mark
Checks for optimization in counting good nodes during traversal instead of post-processing.
常见陷阱
外企场景- error
Failing to track parent nodes can lead to revisiting edges and incorrect counts.
- error
Incorrectly calculating subtree sizes can misclassify good nodes.
- error
Not handling leaf nodes separately may cause off-by-one errors in counting.
进阶变体
外企场景- arrow_right_alt
Count nodes where all subtrees differ in size instead of being equal.
- arrow_right_alt
Apply the good node definition to an N-ary tree instead of a binary tree.
- arrow_right_alt
Return a list of all good node indices rather than just the count.