# 797. All Paths From Source to Target

{% embed url="<https://leetcode.com/problems/all-paths-from-source-to-target/>" %}

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

```python
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`

```python
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
```
