共计 1304 个字符，预计需要花费 4 分钟才能阅读完成。
797. All Paths From Source to Target
Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.
The graph is given as follows: the nodes are 0, 1, …, graph.length – 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.
Example:
Input: [[1,2], [3], [3], []]
Output: [[0,1,3],[0,2,3]]
Explanation: The graph looks like this:
0—>1
| |
v v
2—>3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
Note:
The number of nodes in the graph will be in the range [2, 15].
You can print different paths in any order, but you should keep the order of nodes inside one path.
这一题考察的是图的深度优先遍历，要注意的点是：回溯的时候如何清除掉 record 中的数据，只保留到当前节点的数据，之后的数据需要重新填充。刚开始我是用的一个 record，企图通过清空当前节点之后的数据，后来发现不对，record 必须是多个，否则我给 result 添加的 record 就会全部相同。所以只能通过 new 和深拷贝来完成这个目标。
java 代码
class Solution {
List<List<Integer>> result = new LinkedList<List<Integer>>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
int index=0;
for(int x:graph[index]){
List<Integer> record = new LinkedList<>();
record.add(0);
record.add(x);
depthFirst(graph, x, record);
}
return result;
}
public void depthFirst(int[][] graph, int index, List<Integer> record){
if(index==graph.length-1){
result.add(record);
return;
}
if(graph[index]==null){
return;
}
for(int x:graph[index]){
record.add(x);
int size = record.size();
depthFirst(graph, x, record);
List<Integer> temp = new LinkedList<Integer>();
for(int i=0;i<size-1;i++){
temp.add(record.get(i));
}
record = temp;
}
}
}
