797.所有可能的路径

https://leetcode-cn.com/problems/all-paths-from-source-to-target/

一、dfs

因为是有向无环图，所以从起点直接dfs每个邻节点，回溯中记录路径，直到终点记录路径即可，不用考虑重复访问

class Solution:
    def allPathsSourceTarget(self, graph):
        res = []
        n = len(graph)

        def dfs(now, path):
            path.append(now)    #尝试在路径中加入当前节点
            if now == n-1:    #递归出口1：遍历到终点。
                # 记录该路径，并弹出
                res.append(list(path))
                path.pop()
                return
            # 递归遍历每个相邻节点
            for v in graph[now]:
                dfs(v, path)
            path.pop()      #有加入就要有弹出
            return      #递归出口2：全部相邻节点遍历完（如果是空返回可以省略）

        dfs(0, [])
        return res

改进：

递归中不直接修改path，省去很多“恢复现场”的工作

class Solution:
    def allPathsSourceTarget(self, graph):
        res = []
        n = len(graph)

        def dfs(now, path):
            if now == n - 1:  # 递归出口1：遍历到终点。
                res.append(list(path))
                return
            # 递归遍历每个相邻节点
            for v in graph[now]:
                dfs(v, path+[v])

        dfs(0, [0])		#初始默认起点在路径中
        return res