golang 解法, 执行用时: 12 ms, 内存消耗: 5.1 MB, 提交时间: 2023-05-24 09:24:21

func frogPosition(n int, edges [][]int, t int, target int) float64 {
    g := make([][]int, n+1)
    g[1] = []int{0} // 减少额外判断的小技巧
    for _, e := range edges {
        x, y := e[0], e[1]
        g[x] = append(g[x], y)
        g[y] = append(g[y], x) // 建树
    }

    var dfs func(int, int, int) int
    dfs = func(x, fa, leftT int) int {
        if leftT == 0 {
            if x == target { // 恰好到达
                return 1
            }
            return 0
        }
        if x == target {
            if len(g[x]) == 1 { // target 是叶子，停在原地
                return 1
            }
            return 0
        }
        for _, y := range g[x] { // 遍历 x 的儿子 y
            if y != fa { // y 不能是父节点
                prod := dfs(y, x, leftT-1) // 寻找 target
                if prod != 0 {
                    return prod * (len(g[x]) - 1) // 乘上儿子个数，并直接返回
                }
            }
        }
        return 0 // 未找到 target
    }

    prod := dfs(1, 0, t)
    if prod == 0 { // t 秒后不在 target
        return 0
    }
    return 1 / float64(prod)
}

java 解法, 执行用时: 2 ms, 内存消耗: 42.3 MB, 提交时间: 2023-05-24 09:23:27

class Solution {
    public double frogPosition(int n, int[][] edges, int t, int target) {
        List<Integer>[] g = new ArrayList[n + 1];
        Arrays.setAll(g, e -> new ArrayList<>());
        g[1].add(0); // 减少额外判断的小技巧
        for (var e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x); // 建树
        }
        long prod = dfs(g, target, 1, 0, t);
        return prod != 0 ? 1.0 / prod : 0;
    }

    private long dfs(List<Integer>[] g, int target, int x, int fa, int leftT) {
        // t 秒后必须在 target（恰好到达，或者 target 是叶子停在原地）
        if (leftT == 0) return x == target ? 1 : 0;
        if (x == target) return g[x].size() == 1 ? 1 : 0;
        for (int y : g[x]) { // 遍历 x 的儿子 y
            if (y != fa) { // y 不能是父节点
                long prod = dfs(g, target, y, x, leftT - 1); // 寻找 target
                if (prod != 0) 
                    return prod * (g[x].size() - 1); // 乘上儿子个数，并直接返回
            }
        }
        return 0; // 未找到 target
    }
}

python3 解法, 执行用时: 48 ms, 内存消耗: 16.4 MB, 提交时间: 2023-05-24 09:23:07

# 自底向上dfs
class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        g = [[] for _ in range(n + 1)]
        g[1] = [0]  # 减少额外判断的小技巧
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)  # 建树

        def dfs(x: int, fa: int, left_t: int) -> int:
            # t 秒后必须在 target（恰好到达，或者 target 是叶子停在原地）
            if left_t == 0: return x == target
            if x == target: return len(g[x]) == 1
            for y in g[x]:  # 遍历 x 的儿子 y
                if y != fa:  # y 不能是父节点
                    prod = dfs(y, x, left_t - 1)  # 寻找 target
                    if prod: return prod * (len(g[x]) - 1)  # 乘上儿子个数，并直接返回
            return 0  # 未找到 target

        prod = dfs(1, 0, t)
        return 1 / prod if prod else 0

golang 解法, 执行用时: 8 ms, 内存消耗: 5.1 MB, 提交时间: 2023-05-24 09:22:34

func frogPosition(n int, edges [][]int, t int, target int) (ans float64) {
    g := make([][]int, n+1)
    g[1] = []int{0} // 减少额外判断的小技巧
    for _, e := range edges {
        x, y := e[0], e[1]
        g[x] = append(g[x], y)
        g[y] = append(g[y], x) // 建树
    }

    var dfs func(int, int, int, int) bool
    dfs = func(x, fa, leftT, prod int) bool {
        // t 秒后必须在 target（恰好到达，或者 target 是叶子停在原地）
        if x == target && (leftT == 0 || len(g[x]) == 1) {
            ans = 1 / float64(prod)
            return true
        }
        if x == target || leftT == 0 {
            return false
        }
        for _, y := range g[x] { // 遍历 x 的儿子 y
            if y != fa && dfs(y, x, leftT-1, prod*(len(g[x])-1)) {
                return true // 找到 target 就不再递归了
            }
        }
        return false // 未找到 target
    }

    dfs(1, 0, t, 1)
    return
}

java 解法, 执行用时: 2 ms, 内存消耗: 42.1 MB, 提交时间: 2023-05-24 09:22:17

class Solution {
    private double ans;

    public double frogPosition(int n, int[][] edges, int t, int target) {
        List<Integer>[] g = new ArrayList[n + 1];
        Arrays.setAll(g, e -> new ArrayList<>());
        g[1].add(0); // 减少额外判断的小技巧
        for (var e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x); // 建树
        }
        dfs(g, target, 1, 0, t, 1);
        return ans;
    }

    private boolean dfs(List<Integer>[] g, int target, int x, int fa, int leftT, long prod) {
        // t 秒后必须在 target（恰好到达，或者 target 是叶子停在原地）
        if (x == target && (leftT == 0 || g[x].size() == 1)) {
            ans = 1.0 / prod;
            return true;
        }
        if (x == target || leftT == 0) return false;
        for (int y : g[x])  // 遍历 x 的儿子 y
            if (y != fa && dfs(g, target, y, x, leftT - 1, prod * (g[x].size() - 1)))
                return true; // 找到 target 就不再递归了
        return false; // 未找到 target
    }
}

python3 解法, 执行用时: 44 ms, 内存消耗: 16.4 MB, 提交时间: 2023-05-24 09:21:57

# 自顶向下，dfs
class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        g = [[] for _ in range(n + 1)]
        g[1] = [0]  # 减少额外判断的小技巧
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)  # 建树
        ans = 0

        def dfs(x: int, fa: int, left_t: int, prod: int) -> True:
            # t 秒后必须在 target（恰好到达，或者 target 是叶子停在原地）
            if x == target and (left_t == 0 or len(g[x]) == 1):
                nonlocal ans
                ans = 1 / prod
                return True
            if x == target or left_t == 0: return False
            for y in g[x]:  # 遍历 x 的儿子 y
                if y != fa and dfs(y, x, left_t - 1, prod * (len(g[x]) - 1)):
                    return True  # 找到 target 就不再递归了
            return False  # 未找到 target

        dfs(1, 0, t, 1)
        return ans