苏州网站开发公司济南兴田德润厉害吗/网站如何进行seo

剑指 Offer II 110. 所有路径【中等题】

思路：【回溯】

定义ans记录所有0 ~ n-1 路径，定义 list 记录当前路径。
初始状态，路径list从0开始。

定义 dfs 函数进行深度优先搜索，dfs的传入参数为 list，graph，当前节点idx，ans。

首先判断当前节点idx是否是终止节点 n-1，如果是，则将当前路径添加到ans中，dfs函数返回；
如果不是，那么遍历当前节点可指向的下一个节点，将下一个节点添加到list中，并调用dfs函数筛选路径，筛选结束进行回溯，恢复筛选前状态。

代码：

class Solution {public List<List<Integer>> allPathsSourceTarget(int[][] graph) {List<List<Integer>> ans = new ArrayList<>();List<Integer> list = new ArrayList<>();list.add(0);dfs(list,graph,0,ans);return ans;}public void dfs(List<Integer> list,int[][] graph,int idx,List<List<Integer>> ans){if (idx == graph.length - 1){ans.add(new ArrayList<>(list));return;}for (int i = 0; i < graph[idx].length; i++) {list.add(graph[idx][i]);dfs(list,graph,graph[idx][i],ans);list.remove(list.get(list.size()-1));}}
}