力扣 797. 所有可能的路径_力扣输出图的所有路径

题目来源：https://leetcode-cn.com/problems/all-paths-from-source-to-target/

大致题意：
给定一个有向无环图，找出从 0 至 n-1 有多少条路径，输出所有的路径

思路

dfs

直接 dfs，从 0 点出发，使用栈记录当前路径，若递归到 n-1， 则把栈的内容取出即可。

代码：

 	List<List<Integer>> pathList = new ArrayList<List<Integer>>();
    // 使用双向队列做栈
    Deque<Integer> stack = new ArrayDeque<Integer>();
    int n;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        n = graph.length;
        // 添加起始节点
        stack.offerLast(0);
        dfs(0, graph);
        return pathList;
    }
    public void dfs(int point, int[][] graph) {
        // 若遍历到目的点
        if (point == n-1) {
            List<Integer> list = new ArrayList<Integer>(stack);
            // 当前栈内容放入列表
            pathList.add(list);
            return;
        }
        for (int to : graph[point]) {
            // 递归遍历当前点，入栈
            stack.offerLast(to);
            dfs(to, graph);
            // 递归结束，出栈
            stack.pollLast();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27