797. All Paths From Source to Target

https://leetcode.com/problems/all-paths-from-source-to-target/

solution

# 不判断visited 反而更快, 因为本题输入明确为：有向无环图（DAG）

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        if not graph:
            return [[]]
        path = [0]
        result = []
        visited = {}
        self.dfs(path, result, graph, visited)
        return result

    def dfs(self, path, result, graph, visited):
        if path[-1] == len(graph) - 1:
            result.append(path[:])
            return
        
        for i in graph[path[-1]]:
            if i not in visited or not visited[i]:
                visited[i] = True
                path.append(i)
                self.dfs(path, result, graph, visited)
                path.pop(-1)
                visited[i] = False            

时间复杂度：O() 空间复杂度：O(Edges) + O(Nodes)

follow up

62. Unique Paths

path sum of binary tree

class solution:
    def __init__(self):
        self.res = []
    
    def dfs(self, node: Node, sum:int):
        sum += node.val
        if not node.left and not node.right:
            self.res.append(sum)
            return
        
        if node.left:
            self.dfs(node.left, sum)
        
        if node.right:
            self.dfs(node.right, sum)
    
    def pathSum(self, root: Node):
        if not root:
            return self.res
        self.dfs(root, 0)
        return self.res