Description

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.

Solution

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        def dfs(root,sum,path):
            if root is None:
                return
            if sum ==root.val and not root.left and not root.right:
                self.path.append(path+[root.val])
                return
            dfs(root.left,sum-root.val,path+[root.val])
            dfs(root.right,sum-root.val,path+[root.val])
            
        self.path=[]
        dfs(root,sum,[])
        return self.path
        
        ```