Qwen模型 LeetCode 2603. 收集树中金币 Java实现

哎呀，这道题我可太熟啦！2603. 收集树中金币，看着挺复杂的，其实想通了就特别有意思～让我跟你聊聊我的思路～

这题本质上是个树形DP问题，我们需要在无向树上进行两次遍历。先说说我的理解哈：想象你在一个巨大的树形迷宫里，有些房间里有金币，你要想办法收集所有金币，但是每次移动都要花力气，所以得规划最优路线。

**核心思路分三步走：**
1️⃣ 先从叶子节点往上看，判断哪些子树根本没必要去（因为没金币也留不住）
2️⃣ 把那些"光秃秃"的枝条剪掉
3️⃣ 最后计算剩下的结构需要多少步

```java
import java.util.*;

public class Solution {
public int collectTheCoins(int[] coins, int[][] edges) {
int n = coins.length;
if (n <= 3) return 0; // 特判：三个节点以内直接搞定

// 建图
List<Set<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new HashSet<>());
}

for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}

// 第一步：拓扑排序，去掉没有金币且度为1的叶子节点
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (graph.get(i).size() == 1 && coins[i] == 0) {
queue.offer(i);
}
}

while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : graph.get(u)) {
graph.get(v).remove(u);
if (coins[v] == 0 && graph.get(v).size() == 1) {
queue.offer(v);
}
}
graph.get(u).clear();
}

// 第二步：再进行两次拓扑排序，去掉最外层两层节点
for (int round = 0; round < 2; round++) {
queue.clear();
for (int i = 0; i < n; i++) {
if (graph.get(i).size() == 1) {
queue.offer(i);
}
}

while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : graph.get(u)) {
graph.get(v).remove(u);
}
graph.get(u).clear();
}
}

// 统计剩余边数，每条边要走两次
int edgesLeft = 0;
for (int i = 0; i < n; i++) {
edgesLeft += graph.get(i).size();
}

return Math.max(0, edgesLeft);
}
}
```

诶，你觉得这个解法怎么样？我刚开始做这题的时候也被绕晕过，特别是那个"必须经过有金币的节点"的条件。后来想到用拓扑排序一层层剥洋葱的方式，就清晰多了。

对了，最近你在刷树相关的题目吗？这类题真的很有意思，像在解一个个小谜题。我记得上周我还为了弄明白一个类似的题，画了好多树状图呢～要不要一起讨论下其他变种题型？