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.

Example:

Given the below binary tree and sum = 22,


      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1


Return:


[
   [5,4,11,2],
   [5,8,4,5]
]

Difficulty: interview

Starter code:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        

Solutions:
# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def pathSum(self, root, sum):
         """
         :type root: TreeNode
         :type sum: int
         :rtype: List[List[int]]
         """
         ans = []
         buffer = []
         self.helper(ans, root, sum, buffer)
         return ans
     def helper(self, ans, root, sum, buffer):
         """
         recursive method travesal to the bottom of the tree
         and add the path that path's sum equals the given sum into the result
         
         :type ans: List[List[int]]
         :type root: TreeNode
         :type sum: int
         :type buffer: List[int]
         :rtype None
         """
         if not root: return
         sum -= root.val
         buffer.append(root.val)
         if not (root.left or root.right) and sum == 0: ans.append([x for x in buffer])
         self.helper(ans, root.left, sum, buffer)
         self.helper(ans, root.right, sum, buffer)
         buffer.pop()

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def pathSum(self, root, sum):
         return self.preorder(root, sum, [], [])
     
     def preorder(self, root, sum, path, list):
         
         if not root:
             return []
         
         path = path[:]
         path.append(root.val)
     
         if not root.left and not root.right and root.val == sum:
             list.append(path)
             
         if root.left or root.right:
             sum -= root.val
                 
         if root.left:
             list = self.preorder(root.left, sum, path, list)
 
         if root.right:
             list = self.preorder(root.right, sum, path, list)
             
 
         return list

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def pathSum(self, root, sum):
         """
         :type root: TreeNode
         :type sum: int
         :rtype: List[List[int]]
         """
         res = []
 
         def _helper(node, path, tmp_sum):
             if not node:
                 return
             tmp_sum += node.val
             path.append(node.val)
             if tmp_sum == sum and not node.left and not node.right:
                 res.append(path.copy())
             if node.left:
                 _helper(node.left, path, tmp_sum)
             if node.right:
                 _helper(node.right, path, tmp_sum)
             path.pop()
             tmp_sum -= node.val
 
         _helper(root, [], 0)
         return res

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 import copy
 class Solution:
     def dfs(self, root, sum, cur_path, cur_sum, path):
         if root.left == None and root.right == None:
             if cur_sum + root.val == sum:
                 cur_path.append(root.val)
                 path.append(copy.deepcopy(cur_path))
                 cur_path.pop()
         if root.left != None:
             cur_path.append(root.val)
             self.dfs(root.left, sum, cur_path, cur_sum + root.val, path)
             cur_path.pop()
         if root.right != None:
             cur_path.append(root.val)
             self.dfs(root.right, sum, cur_path, cur_sum + root.val, path)
             cur_path.pop() 
     
     def pathSum(self, root, sum):
         """
         :type root: TreeNode
         :type sum: int
         :rtype: List[List[int]]
         """
         if root == None:
             return []
         path = []
         self.dfs(root, sum, [], 0, path)
         return path
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def pathSum(self, root, sum):
         """
         :type root: TreeNode
         :type sum: int
         :rtype: List[List[int]]
         """
         if not root:
             return []
         res = []
         q = collections.deque([(root, root.val, [root.val])])
         while q:
             r, v, ls = q.popleft()
             if not r.left and not r.right and v == sum:
                 res.append(ls)
             if r.left:
                 q.append((r.left, v+r.left.val, ls+[r.left.val]))
             if r.right:
                 q.append((r.right, v+r.right.val, ls+[r.right.val]))
         return res

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def pathSum(self, root, sum):
         """
         :type root: TreeNode
         :type sum: int
         :rtype: List[List[int]]
         """
         result = []
         def helper(root,target,sum,cur_result):
             if not root:
                 return
             target-=root.val
             cur_result.append(root.val)
             if target == 0 and not root.left and not root.right:
                 result.append([i for i in cur_result])
             helper(root.left,target,sum,cur_result)    
             helper(root.right,target,sum,cur_result)    
             cur_result.pop()
         helper(root,sum,0,[])    
         return result 

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def pathSum(self, root, sum):
         """
         :type root: TreeNode
         :type sum: int
         :rtype: List[List[int]]
         """
         if root is None:
             return []
         if not (root.left or root.right) and root.val == sum:
             return [[root.val]]
         return [[root.val]+ans for ans in self.pathSum(root.left,sum-root.val)+self.pathSum(root.right,sum-root.val)]

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def pathSum(self, root, sum):
         """
         :type root: TreeNode
         :type sum: int
         :rtype: List[List[int]]
         """
         _, res = self.recPathSum(root, sum)
         return res
     
     def recPathSum(self, root, sum):
         if not root:
             return (False, [])
         if root.val == sum:
             if not root.left and not root.right:
                 return (True, [[root.val]])
         foundLeft, listLeft = self.recPathSum(root.left, sum - root.val)
         foundRight, listRight = self.recPathSum(root.right, sum - root.val)
         res = []
         if foundLeft:
             res = [[root.val] + l for l in listLeft]
         if foundRight:
             res += [[root.val] + l for l in listRight]
         return (foundLeft or foundRight, res)

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def pathSum(self, root, sum):
         """
         :type root: TreeNode
         :type sum: int
         :rtype: List[List[int]]
         """
         self.ret=[]
         self.DFS(root,sum,[])
         return(self.ret)
     def DFS(self,roots,nums,valList):
         if(roots==None):
             return()
         if(roots.left==None and roots.right==None and nums==roots.val):
             self.ret.append(valList+[roots.val])
         self.DFS(roots.left,nums-roots.val,valList+[roots.val])
         self.DFS(roots.right,nums-roots.val,valList+[roots.val])
         
         
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def pathSum(self, root, sums):
         """
         :type root: TreeNode
         :type sum: int
         :rtype: List[List[int]]
         """
         self.ret = []
         def dfs(root, s, path):
             if root.left is None and root.right is None:
                 if s == sums:
                     self.ret.append(path)
                 return
             if root.left:
                 dfs(root.left, s+root.left.val, path + [root.left.val])
             if root.right:
                 dfs(root.right, s+root.right.val, path + [root.right.val])
         if not root:return []
         dfs(root, root.val, [root.val])
         return self.ret


# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def pathSum(self, root, sum):
         """
         :type root: TreeNode
         :type sum: int
         :rtype: List[List[int]]
         """
         curr_path = []
         if root == None:
             return curr_path
         else:
             return self.pathSumHelper(root, sum, curr_path)
         
     def pathSumHelper(self, root, sum, curr_path):
         new_path = curr_path + [root.val]
         if root.left is None and root.right is None:
             return [new_path] if sum == root.val else []
         elif root.left is None:
             return self.pathSumHelper(root.right, sum - root.val, new_path)
         elif root.right is None:
             return self.pathSumHelper(root.left, sum - root.val, new_path)
         else:
             return self.pathSumHelper(root.right, sum - root.val, new_path) + self.pathSumHelper(root.left, sum - root.val, new_path)

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 stack1 = []
 stack2 = []
 class Solution:
     def pathSum(self, root, sum):
         """
         :type root: TreeNode
         :type sum: int
         :rtype: List[List[int]]
         """
         def dfs(root, currsum, valuelist):
             if root.left==None and root.right==None:
                 if currsum==sum: res.append(valuelist)
             if root.left:
                 dfs(root.left, currsum+root.left.val, valuelist+[root.left.val])
             if root.right:
                 dfs(root.right, currsum+root.right.val, valuelist+[root.right.val])
         
         res=[]
         if root==None: return []
         dfs(root, root.val, [root.val])
         return res

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def pathSum(self, root, sum):
         """
         :type root: TreeNode
         :type sum: int
         :rtype: List[List[int]]
         """
         if not root:
             return []
         
         res = []
         
         stack = [ (root, root.val, [root.val]) ]
         
         while stack:
             curr, currsum, currp = stack.pop()
             if not curr.left and not curr.right:
                 if currsum == sum:
                     res.append( currp )
             for child in [curr.left, curr.right]:
                 if child:
                     stack.append( (child, currsum + child.val, currp + [child.val]) )
         
         return res