题目：
思路：
反复利用path去记录路径，一旦到达末尾，将path的最后一个值删去，再用new LinkedList(path) 新建一个对象存入结果
注意：
由于该图是无环的，不需要maiked 数组来标记每个是否访问过；
每个路径结束都要向List<List< Integer >>中存入一个List< Integer >对象，每次需要new出来 ！LinkedList<>的有参构造可以方任意Collection的子类
题目规定了只从顶点0开始，所以只有一个for去遍历顶点0的邻接表；
removeLast（） 是LinkedList的方法， 所以不能使用List<Integer> path=new LinkedList<>();去创建path ！由于静态绑定，List没有removeLast方法，所以编译不通过。
Java实现：
class Solution {
List<List<Integer>> r=new LinkedList<>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
//graph是邻接表，每个元素是一个数组，存有该顶点相连的其他顶点
LinkedList<Integer> path=new LinkedList<>(); //多态，LinkedList才有removerLast()方法！
traverse(graph,0,path);
return r;
}
void traverse(int[][]graph,int s,LinkedList<Integer> path){
path.add(s); // 先添加起始节点
//判断是否迭代到头了,是则完成一个路径
int n=graph.length;
if(s==n-1){
r.add(new LinkedList<>(path)); // 传进来只有一个path对象，而r中要有多个List对象 ！ 每个路径需要new一个List对象 ！
path.removeLast();//递归完成，移除path中元素，
return;
}
//dfs
for(int k :graph[s]){ // 遍历当前节点s的邻接表
traverse(graph,k,path);
}
path.removeLast(); //递归完成，移除path中元素，
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89267.html
