力扣刷題筆記——第797題. 所有可能的路徑

第797題. 所有可能的路徑

參考題解：官方題解

題目：

标簽：

• 深度優先周遊。

思路：

• 這道題思路是很簡單的。而且是有向無環圖，都不用考慮環了。這種題是面試必須要會的。
• 不過，這道題有一些 Java 語言的文法細節很有意思，如果不熟練可能會吃虧。
• 首先，Deque 的使用。Deque 我個人認為是比 Queue 更好用的類型，就是雙端隊列，左右兩側都可以添加和删除，實作類有 ArrayDeque 和 LinkedList，方法是 offerFirst、pollFirst、offerLast、pollLast。
• 其次，是 Collections 集合類内部的類型轉換。例如 ArrayList 和 ArrayDeque 如何互相轉換。可以直接類型強制轉換就行，将原内容放到

  new 新内容類型<資料類型>(原内容)

  中的括号裡面就可以了。
• 最後，遞歸可以采用

  stack.offerLast(y); dfs(graph, y, n); stack.pollLast();

  實作。

題解：

class Solution {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    Deque<Integer> stack = new ArrayDeque<Integer>();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        stack.offerLast(0);
        dfs(graph, 0, graph.length - 1);
        return ans;
    }

    public void dfs(int[][] graph, int x, int n) {
        if (x == n) {
            ans.add(new ArrayList<Integer>(stack));
            return;
        }
        for (int y : graph[x]) {
            stack.offerLast(y);
            dfs(graph, y, n);
            stack.pollLast();
        }
    }
}