M-113. Path Sum II

Loading...LeetCode

dfs在二叉树里面就是pre order traverse

# 0 
class Solution:
    def __init__(self):
        self.paths = []
        
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        def path_count_helper(root, cur_path, sum):
            if not root:
                return 
            sum -= root.val
            cur_path.append(root.val)
            if not root.left and not root.right:
                if sum == 0:
                    self.paths.append(cur_path)
                return
            path_count_helper(root.left , cur_path.copy(), sum)
            path_count_helper(root.right, cur_path.copy(), sum)
            
        
        path_count_helper(root, [], sum)
        return self.paths
# 1: https://leetcode.com/problems/path-sum-ii/discuss/36829/Python-solutions-(Recursively-BFS%2Bqueue-DFS%2Bstack)