LeetCode 797：所有可能的路径

链接

题目：

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.removeLast();//递归完成，移除path中元素，
                return;
            }
            //dfs
            for(int k :graph[s]){
    
                traverse(graph,k,path);
            }
            path.removeLast(); //递归完成，移除path中元素，
        } 
}