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]
]
# 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
 
 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)