Qwen模型 LeetCode 2581. 统计可能的树根数目 Java实现

哇！这道2581题超有趣的，让我来给你讲讲我的解法~ 这道题就像是在玩侦探游戏，我们要找出所有可能的"树根"嫌疑人！

题目大意是：给我们一些从树中删除边的信息，让我们推断出哪些节点可能成为原来的树根。这就像是案发现场只留下了脚印，我们要还原整个故事。

```java
import java.util.*;

public class Solution {
public int rootCount(int[][] edges, int[][] guesses, int k) {
int n = edges.length + 1; // 节点数量

// 构建邻接表表示的树
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}

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

// 将guesses转换为Set方便快速查找
Set<String> guessSet = new HashSet<>();
for (int[] guess : guesses) {
guessSet.add(guess[0] + "," + guess[1]);
}

// 第一次DFS：以0为根，计算初始猜对次数
int[] correctGuesses = {0};
boolean[] visited = new boolean[n];

dfs(0, -1, graph, guessSet, correctGuesses);

// 第二次DFS：换根DP
int[] result = {0};
reRootDfs(0, -1, graph, guessSet, correctGuesses[0], k, result);

return result[0];
}

// 第一次DFS：计算以0为根时猜对的次数
private void dfs(int node, int parent, List<List<Integer>> graph,
Set<String> guessSet, int[] correctGuesses) {
for (int child : graph.get(node)) {
if (child == parent) continue;

// 检查这条边是否被正确猜测
if (guessSet.contains(node + "," + child)) {
correctGuesses[0]++;
}

dfs(child, node, graph, guessSet, correctGuesses);
}
}

// 换根DFS
private void reRootDfs(int node, int parent, List<List<Integer>> graph,
Set<String> guessSet, int currentCorrect, int k, int[] result) {

// 如果当前根节点满足条件
if (currentCorrect >= k) {
result[0]++;
}

for (int child : graph.get(node)) {
if (child == parent) continue;

// 计算换根后的正确猜测数
int newCorrect = currentCorrect;

// 移除node->child这条边的影响
if (guessSet.contains(node + "," + child)) {
newCorrect--;
}
// 添加child->node这条边的影响
if (guessSet.contains(child + "," + node)) {
newCorrect++;
}

reRootDfs(child, node, graph, guessSet, newCorrect, k, result);
}
}
}
```

诶，你知道吗？这道题最精妙的地方在于"换根DP"的思想。就像是一棵树在旋转，每次把一个子节点变成新的根节点，我们只需要考虑边的方向变化带来的影响。

我来打个比方：想象你有一串圣诞灯，每个灯泡都可以当作电源插头。当我们把插头从一个灯泡换到另一个时，只需要关心它们之间那条线的电流方向变了没，其他线路都不用重新检查！

这个算法的时间复杂度是O(n)，超级高效有没有？而且思路特别清晰：先固定一个根统计答案，然后通过遍历的方式"转动"这棵树，动态维护猜对的次数。

你最近是在准备面试吗？这种换根DP的题目在大厂面试中还挺常见的。要是想练更多类似的题目，我可以给你推荐几道经典的~要不要来个"树形DP特训"？😄