113. Path Sum II

# Medium

Similar to #112.

Be carefull to operate list, the defaul copy is deep copy.

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        paths = []
        path = []
        
        if root == None:
            return paths
        
        self.pathRecord(root, sum, paths, path)
        return paths
    
    def pathRecord(self, root, sum, paths, path):
        # edge case
        path.append(root.val)
        path_o = path[:]

        if root.left == None and root.right == None:
            if root.val == sum:
                paths.append(path)
            return
        
        # regular case
        if root.left != None:
            self.pathRecord(root.left, sum-root.val, paths, path)
        if root.right != None:
            path = path_o[:]
            self.pathRecord(root.right, sum-root.val, paths, path)
            

Second Tab

Time complexity = $O(n)$ , space complexity = $O(1)$ . Because the worst case is to traversal all nodes and each node only bring one information True or False.