给你一棵由 n 个顶点组成的无向树，顶点编号从 1 到 n。青蛙从 顶点 1 开始起跳。规则如下：
在一秒内，青蛙从它所在的当前顶点跳到另一个 未访问 过的顶点（如果它们直接相连）。
青蛙无法跳回已经访问过的顶点。
如果青蛙可以跳到多个不同顶点，那么它跳到其中任意一个顶点上的机率都相同。
如果青蛙不能跳到任何未访问过的顶点上，那么它每次跳跃都会停留在原地。
无向树的边用数组 edges 描述，其中 edges[i] = [ai, bi] 意味着存在一条直接连通 ai 和 bi 两个顶点的边。
返回青蛙在 t 秒后位于目标顶点 target 上的概率。与实际答案相差不超过 10-5 的结果将被视为正确答案。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/frog-position-after-t-seconds
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
import java.util.*;
class Solution {
private Map<Integer, Set<Integer>> buildGraph(int[][] edges) {
if (edges == null || edges.length == 0 || edges[0].length == 0) {
return Collections.emptyMap();
}
Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
int from = edge[0];
int to = edge[1];
Set<Integer> toList = graph.getOrDefault(from, new HashSet<>());
toList.add(to);
graph.put(from, toList);
Set<Integer> fromList = graph.getOrDefault(to, new HashSet<>());
fromList.add(from);
graph.put(to, fromList);
}
return graph;
}
public double frogPosition(int n, int[][] edges, int t, int target) {
Map<Integer, Set<Integer>> graph = buildGraph(edges);
boolean[] visited = new boolean[n + 1];
return dfs(graph, 1, target, t, visited);
}
private double dfs(Map<Integer, Set<Integer>> graph, int from, int target, int t, boolean[] visited) {
Set<Integer> toSet = graph.getOrDefault(from, Collections.emptySet());
int cnt = from == 1 ? toSet.size() : toSet.size() - 1;
if (t == 0 || cnt == 0) {
return from == target ? 1 : 0;
}
visited[from] = true;
double ans = 0;
for (int to : toSet) {
if (!visited[to]) {
ans += dfs(graph, to, target, t - 1, visited);
}
}
return ans / cnt;
}
}