当然可以这次我给你一个**更精炼、更 Pythonic、逻辑清晰又高效**的 Python3 实现还附带了详细的思路说明和小技巧✨这道题的本质是**在树上剪枝两次后剩下的边数 × 2 就是答案**。为什么因为- 第一次剪掉所有“没金币的叶子”白跑一趟不如不去- 再剪掉最外两层走到金币就可以返程外层不用回---### ✅ Python3 实现简洁 高效pythonfrom collections import deque, defaultdictclass 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)) // 2return remaining_edges * 2---### 为什么这样写- **defaultdict(set)**自动处理未出现的节点且 set 支持快速删除。- **discard() 而不是 remove()**避免 KeyError更安全虽然这里不会出错但好习惯。- **列表推导式初始化队列**Python 的优雅之处一行搞定初始叶子。- **两次剪枝独立进行**逻辑清晰不易出错。---### 举个小例子理解比如pythoncoins [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 树专题这类“剪枝 拓扑”的思路特别实用要不要我再给你讲讲怎么用类似方法解决“收集苹果的最小时间”那道题
Qwen模型 LeetCode 2603. 收集树中金币 Python3实现
当然可以这次我给你一个**更精炼、更 Pythonic、逻辑清晰又高效**的 Python3 实现还附带了详细的思路说明和小技巧✨这道题的本质是**在树上剪枝两次后剩下的边数 × 2 就是答案**。为什么因为- 第一次剪掉所有“没金币的叶子”白跑一趟不如不去- 再剪掉最外两层走到金币就可以返程外层不用回---### ✅ Python3 实现简洁 高效pythonfrom collections import deque, defaultdictclass 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)) // 2return remaining_edges * 2---### 为什么这样写- **defaultdict(set)**自动处理未出现的节点且 set 支持快速删除。- **discard() 而不是 remove()**避免 KeyError更安全虽然这里不会出错但好习惯。- **列表推导式初始化队列**Python 的优雅之处一行搞定初始叶子。- **两次剪枝独立进行**逻辑清晰不易出错。---### 举个小例子理解比如pythoncoins [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 树专题这类“剪枝 拓扑”的思路特别实用要不要我再给你讲讲怎么用类似方法解决“收集苹果的最小时间”那道题
