1377. T 秒后青蛙的位置

给你一棵由 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;
    }
}