LeetCode 题解工作台
收集树中金币
给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [a i , b i ] 表示树中节点 a i 和 b i 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 图
答案摘要
我们先将 中的边转换成邻接表 ，其中 表示节点 的所有邻接节点，用集合表示。 接下来我们遍历所有节点，找到 且 中只有一个节点的节点（也即是金币为 的叶子节点），将其加入队列 中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图 题型思路
题目描述
给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。
一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：
- 收集距离当前节点距离为
2以内的所有金币，或者 - 移动到树中一个相邻节点。
你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。
如果你多次经过一条边，每一次经过都会给答案加一。
示例 1：
输入：coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]] 输出：2 解释：从节点 2 出发，收集节点 0 处的金币，移动到节点 3 ，收集节点 5 处的金币，然后移动回节点 2 。
示例 2：
输入：coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]] 输出：2 解释：从节点 0 出发，收集节点 4 和 3 处的金币，移动到节点 2 处，收集节点 7 处的金币，移动回节点 0 。
提示：
n == coins.length1 <= n <= 3 * 1040 <= coins[i] <= 1edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biedges表示一棵合法的树。
解题思路
方法一：拓扑排序
我们先将 中的边转换成邻接表 ，其中 表示节点 的所有邻接节点，用集合表示。
接下来我们遍历所有节点，找到 且 中只有一个节点的节点（也即是金币为 的叶子节点），将其加入队列 中。
然后我们不断地从队列中取出节点，将其从邻接表中删除，然后判断其邻接节点是否满足 且 中只有一个节点的条件，如果满足则将其加入队列 中。循环，直至队列为空。
经过上述操作后，我们得到了一棵新的树，且树的叶子节点都是金币为 的节点。
然后，我们再删除剩下的两层叶子节点，最终得到的是一棵所有节点都需要被访问的节点，我们只需要统计其边数，乘上 ，即为答案。
时间复杂度 ，空间复杂度 。其中 为节点数。
相似题目：
class Solution:
def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:
g = defaultdict(set)
for a, b in edges:
g[a].add(b)
g[b].add(a)
n = len(coins)
q = deque(i for i in range(n) if len(g[i]) == 1 and coins[i] == 0)
while q:
i = q.popleft()
for j in g[i]:
g[j].remove(i)
if coins[j] == 0 and len(g[j]) == 1:
q.append(j)
g[i].clear()
for k in range(2):
q = [i for i in range(n) if len(g[i]) == 1]
for i in q:
for j in g[i]:
g[j].remove(i)
g[i].clear()
return sum(len(g[a]) > 0 and len(g[b]) > 0 for a, b in edges) * 2
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the approach chosen, but typically a DFS with pruning will run in O(n) time, where n is the number of nodes. The space complexity will also be O(n) due to the recursive stack and storage of visited nodes and coin positions. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Looks for understanding of tree traversal and pruning techniques.
- question_mark
Evaluates candidate's ability to optimize graph traversal through topological ordering.
- question_mark
Assesses if the candidate can identify redundant nodes and edges in tree problems.
常见陷阱
外企场景- error
Failing to prune unnecessary nodes that don't affect the coin collection.
- error
Not considering optimal traversal order leading to redundant path explorations.
- error
Overlooking the fact that all leaf nodes without coins are irrelevant to the problem.
进阶变体
外企场景- arrow_right_alt
Variation 1: The tree is directed and includes cycles.
- arrow_right_alt
Variation 2: The tree is rooted and requires a specific root for traversal.
- arrow_right_alt
Variation 3: Add restrictions on the number of times you can traverse an edge.