哎呀这道题我可太熟啦2603. 收集树中金币看着挺复杂的其实想通了就特别有意思让我跟你聊聊我的思路这题本质上是个树形DP问题我们需要在无向树上进行两次遍历。先说说我的理解哈想象你在一个巨大的树形迷宫里有些房间里有金币你要想办法收集所有金币但是每次移动都要花力气所以得规划最优路线。**核心思路分三步走**1️⃣ 先从叶子节点往上看判断哪些子树根本没必要去因为没金币也留不住2️⃣ 把那些光秃秃的枝条剪掉3️⃣ 最后计算剩下的结构需要多少步javaimport java.util.*;public class Solution {public int collectTheCoins(int[] coins, int[][] edges) {int n coins.length;if (n 3) return 0; // 特判三个节点以内直接搞定// 建图ListSetInteger 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的叶子节点QueueInteger 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);}}诶你觉得这个解法怎么样我刚开始做这题的时候也被绕晕过特别是那个必须经过有金币的节点的条件。后来想到用拓扑排序一层层剥洋葱的方式就清晰多了。对了最近你在刷树相关的题目吗这类题真的很有意思像在解一个个小谜题。我记得上周我还为了弄明白一个类似的题画了好多树状图呢要不要一起讨论下其他变种题型
