# 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]]
        """
        answer = []
        if root:
            self.helper(root, [], answer, sum)
        return answer

    def helper(self, root, path, answer, target):
        print('root.val:', root.val, 'path:', path, 'answer:', answer)
        if root.left is None and root.right is None:
            if sum(path + [root.val]) == target:
                answer.append(path + [root.val])
        if root.left:
            self.helper(root.left, path + [root.val], answer, target)
        if root.right:
            self.helper(root.right, path + [root.val], answer, target)


mytree = TreeNode(1)
mytree.left = TreeNode(2)
mytree.right = TreeNode(3)
mytree.right.left = TreeNode(12)

test = Solution()
print(test.pathSum(mytree, 3))
