需要记录走过路径上的值, 我另外用了一个currSum变量来记录当前valList中所有数的和, 省去了sum(valList), 可以节省一些时间。Solution.res 和 Solution.Sum是类变量, 每一个getPath函数都可以访问它们。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @param sum, an integer
    # @return a list of lists of integers
    def pathSum(self, root, Sum):
        if root == None: return []
        Solution.res = []
        Solution.Sum = Sum
        self.getPath(root, [root.val], root.val)
        return Solution.res
        
    def getPath(self, root, valList, currSum):
        if root.left == None and root.right == None:
            if currSum == Solution.Sum: Solution.res.append(valList)
            return
        if root.left:
            self.getPath(root.left, valList + [root.left.val], currSum + root.left.val)
        if root.right:
            self.getPath(root.right, valList + [root.right.val], currSum + root.right.val)