# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

import copy

class Solution(object):

    

    def find_paths(self,root,sum,paths,path_tmp):

        

        path_tmp.append(root.val)

        sum = sum-root.val

        if root.left == None and root.right == None and sum == 0:

            paths.append(copy.deepcopy(path_tmp))

         

        else:

        

            if root.left != None:

                self.find_paths(root.left,sum,paths,path_tmp)

        

            if root.right != None:

                self.find_paths(root.right,sum,paths,path_tmp)

        

        sum = sum +root.val

        path_tmp.pop()

        return

    

    def pathSum(self, root, sum):

        """

        :type root: TreeNode

        :type sum: int

        :rtype: List[List[int]]

        """

        paths=[]

        path_tmp=[]

        

        if root != None:

            self.find_paths(root,sum,paths,path_tmp)

            

        return paths