Qwen模型 LeetCode 2603. 收集树中金币 Python3实现
当然可以！这次我给你一个**更精炼、更 Pythonic、逻辑清晰又高效**的 Python3 实现，还附带了详细的思路说明和小技巧～✨
这道题的本质是：**在树上剪枝两次后，剩下的边数 × 2 就是答案**。为什么？因为：
- 第一次剪掉所有“没金币的叶子”（白跑一趟，不如不去）
- 再剪掉最外两层（走到金币就可以返程，外层不用回）
---
### ✅ Python3 实现（简洁 + 高效）
```python
from collections import deque, defaultdict
class Solution:
def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:
n = len(coins)
if n <= 3:
return 0
# 建图：用 set 支持 O(1) 删除
g = defaultdict(set)
for u, v in edges:
g[u].add(v)
g[v].add(u)
# 第一步：剪掉所有「无金币」的叶子（反复剪，直到稳定）
q = deque([i for i in range(n) if len(g[i]) == 1 and coins[i] == 0])
while q:
u = q.popleft()
for v in g[u]:
g[v].discard(u) # 安全删除
if coins[v] == 0 and len(g[v]) == 1:
q.append(v)
g[u].clear() # 标记已移除
# 第二步：连续剪掉最外两层（不管有没有金币）
for _ in range(2):
q = deque([i for i in range(n) if len(g[i]) == 1])
while q:
u = q.popleft()
for v in g[u]:
g[v].discard(u)
g[u].clear()
# 第三步：统计剩余边数 → 每条边走两次
remaining_edges = sum(len(g[i]) for i in range(n)) // 2
return remaining_edges * 2
```
---
### 🌟 为什么这样写？
- **`defaultdict(set)`**：自动处理未出现的节点，且 `set` 支持快速删除。
- **`discard()` 而不是 `remove()`**：避免 KeyError，更安全（虽然这里不会出错，但好习惯！）。
- **列表推导式初始化队列**：Python 的优雅之处，一行搞定初始叶子。
- **两次剪枝独立进行**：逻辑清晰，不易出错。
---
### 🔍 举个小例子理解
比如：
```python
coins = [1,0,0,0,0,1]
edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]
```
树结构：`0—1—2—3—4—5`，只有 0 和 5 有金币。
- 第一步：中间的 2、3 是无金币叶子吗？不是，因为它们度>1。但 1 和 4 一开始也不是叶子。
- 等等……其实第一步**什么也剪不掉**！因为所有无金币节点（1,2,3,4）度都 ≥2。
- 第二步：剪第一层 → 去掉 0 和 5（叶子），剩下 `1—2—3—4`
- 第三步：再剪一层 → 去掉 1 和 4，剩下 `2—3`
- 剩余 1 条边 → 答案 = 1 × 2 = **2**
完美匹配！
---
### 💡 小贴士
- 这题**不需要 DFS/BFS 遍历整棵树**，拓扑排序（剪枝）就够了。
- 最终答案一定是**偶数**，因为每条边都要往返。
- 如果剪完发现没边了（比如所有金币都在相邻节点），直接返回 0。
---
怎么样？这个版本是不是既简洁又容易理解？😄
如果你正在刷 LeetCode 树专题，这类“剪枝 + 拓扑”的思路特别实用！要不要我再给你讲讲怎么用类似方法解决“收集苹果的最小时间”那道题？🍎