algorithms/python/PathSumII/pathSum.py

"""
Method 1
"""
def pathSum(self, root, sum):
    if not root: return []
    res = []

    def dfs(root, sum, ls, res):
        if not root.left and not root.right and sum == root.val:
            ls.append(root.val)
            res.append(ls)
        if root.left:
            dfs(root.left, sum - root.val, ls + [root.val], res)
        if root.right:
            dfs(root.right, sum - root.val, ls + [root.val], res)

    dfs(root, sum, [], res)
    return res

"""
Method 2
"""
def pathSum(self, root, sum):
    if not root: return []
    if not root.left and not root.right and root.val == sum: return [[root.val]]
    temp = self.pathSum(root.left, sum - root.val) + self.pathSum(root.right, sum - root.val)
    return [[root.val] + i for i in temp]