DFS for traversing all paths
Yifu Liu
139
Interview
  1. Since the graph is acyclic, so visited[] is not needed.
  2. A deep copy is needed due to the curr_list is still pointing to the original memory location when program ends, so deep copy is needed. More info in: https://realpython.com/copying-python-objects/#making-shallow-copies.
class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        
        
#         helper method (DFS)
        def traverse(graph, curr_node, curr_list, res):
            curr_list.append(curr_node)
            if curr_node == length - 1:
                res.append(list(curr_list))
                curr_list.pop(-1)
                return 
            
            for next_node in graph[curr_node]:
                traverse(graph, next_node, curr_list, res)
            curr_list.pop(-1)
        
        
        res = []
        length = len(graph)    
        curr_list = []
        traverse(graph, 0, curr_list, res)
        return res
Comments (0)