力扣 797. 所有可能的路径

题目

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

 graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

示例 1：

输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

示例 2：

输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

提示：

• n == graph.length
• 2 <= n <= 15
• 0 <= graph[i][j] < n
• graph[i][j] != i（即不存在自环）
• graph[i] 中的所有元素 互不相同
• 保证输入为 有向无环图（DAG）

思路

        这题虽然是图，但是如果你熟悉二叉树的遍历或者说你知道回溯的框架代码为什么那么写，其实这题就不难，题目已经明确说了没有环，那么我们就可以省略掉visited数组了，然后剩下的工作其实就是找到每一个节点，然后遍历这个节点所能到达的所有结点，最后收集结果就大功告成了。

代码

         这里和回溯有点儿不同的是回溯是在for循环里面处理数据，而这里是在循环外面处理的数据，具体原因你仔细想一想就能知道，如果在循环里面处理数据，那么根节点是处理不到的，不信你可以试试（手动狗头）。

class Solution {
     List<List<Integer>> res = new LinkedList<>();
    void traverse(int[][] graph,int s,LinkedList<Integer> path){
        //将s添加到路径中
        path.add(s);
        //判断是否到达终点
        if(s==graph.length-1){
//因为  Java 函数参数传的是对象引⽤，所以向  res 中添加path 时需要拷⻉⼀个新的列表，否则最终 res 中的列表都是空的。
           res.add(new LinkedList<>(path));
        }
        //递归每个节点
        for(int v:graph[s]){
            traverse(graph,v,path);
        }
        //从路径中移除当前节点s
        path.removeLast();
    }
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        LinkedList<Integer> path=new LinkedList<>();
        traverse(graph,0,path);
        return res;
    }
}

好啦，分享就到这儿，收工~