在一颗无向树上青蛙从顶点1起跳，问T秒后停留在目标位置的概率
1. 深度优先搜索
问题规模可以进一步递归拆分，概率等于下一个节点到目标概率的平均值
class Solution {
public:
double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
vector<vector<int>> G(n + 1);
for (int i = 0; i < edges.size(); ++i) {//建立邻接表
G[edges[i][0]].push_back(edges[i][1]);
G[edges[i][1]].push_back(edges[i][0]);
}
vector<bool> visited(n+1);//访问标识
return dfs(G, visited, 1, t, target);
}
double dfs(vector<vector<int>>& G, vector<bool>& visited, int i, int t, int target) {
int nxt = i == 1 ? G[i].size() : G[i].size() - 1; //相邻顶点个数
if (t == 0 || nxt == 0) //时间到了，或者到了角落
return i == target ? 1.0 : 0.0; //落在目标返回1.否则返回0
visited[i] = true;
double ans = 0.0;
for (int j : G[i]) //遍历相邻顶点
if (!visited[j])
ans += dfs(G, visited, j, t - 1, target);
return ans / nxt;//概率取平均
}
};