E-NR437. Path Sum III

Loading...LeetCode

# 0 MLE了..
class Solution:
    def __init__(self):
        self.paths = []
        
    def path_sum_for_one(self, root: TreeNode, sum: int) -> List[List[int]]:
        def path_count_helper(root, cur_path, sum):
            if not root:
                return 
            sum -= root.val
            cur_path.append(root.val)
            if sum == 0:
                self.paths.append(cur_path)
            path_count_helper(root.left , cur_path.copy(), sum)
            path_count_helper(root.right, cur_path.copy(), sum)
        path_count_helper(root, [], sum)
    
    def pathSum(self, root: TreeNode, sum: int) -> int:
        def helper(root, sum):
            if not root:
                return 
            self.path_sum_for_one(root, sum)
            helper(root.left, sum)
            helper(root.right, sum)

        helper(root, sum)
        return len(self.paths)