797. All Paths From Source to Target

Loading...LeetCode

当作tree来做BFS（因为要找到所有path），遇到node N-1就停，需要解决的是搜索过程中同步记录已经走的node。

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        res = []
        end = len(graph)-1
        q = collections.deque([[0]])
        while q:
            cur = q.popleft()
            for i in graph[cur[-1]]:
                if i == end:
                    res.append(cur+[i])
                else:
                    q.append(cur+[i])
        return res

DFS也一样做，或者可以改写为backtracking

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        self.res = []
        
        def backtracking(graph, path):
            for i in graph[path[-1]]:
                if i == len(graph)-1:
                    self.res.append(path+[i])
                else:
                    backtracking(graph, path+[i])
        
        backtracking(graph, [0])
        return self.res