1377. Frog Position After T Seconds =================================== 题目信息 -------- :题号: 1377 :难度: Hard :主题: 树、概率、深度优先搜索 :原题: `LeetCode 1377 `_ :重点: 青蛙从节点 ``1`` 开始,每秒等概率跳到尚未访问的相邻节点;没有未访问邻居时留在原地 题目重述 -------- 给定一棵包含 ``n`` 个节点的无向树。青蛙初始位于节点 ``1``。每秒钟,若当前位置存在未访问过的相邻节点,它会从这些节点中等概率选择一个跳过去;若不存在,则继续停留在当前位置。 请返回恰好 ``t`` 秒后青蛙位于 ``target`` 节点的概率。已经访问过的节点不能再次跳入。 ``1 <= n <= 100``,``0 <= t <= 50``,树边数为 ``n-1``。 自建示例 -------- 根的两个孩子被等概率选择: .. code-block:: text 输入:n = 3, edges = [[1,2],[1,3]], t = 1, target = 2 输出:0.5 解释:第一秒从两个未访问邻居中等概率选择。 到达叶节点后会继续停留: .. code-block:: text 输入:同一棵树,t = 2, target = 2 输出:0.5 解释:第一秒到达节点 2 的概率为二分之一,之后没有未访问邻居,因此留在节点 2。