0

I tried to solve the 113. Path Sum II in Leetcode:

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references. A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

My former solution with depth first search algirithm was:

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if root is None:
            return []   
        res = []
        path = []
        def dfs(node, path_sum):
            path_sum -= node.val
            path.append(node.val)
            if node.left is None and node.right is None:
                if path_sum == 0:
                    *res.append(path)*
                    
            if node.left is not None:
                dfs(node.left, path_sum)
            if node.right is not None:
                dfs(node.right, path_sum)
            
            path.pop()
        dfs(root, targetSum)
        return res

but this only returned a list of blank lists as result, then I changed the res.append(path) to res.append(path[:]) and everything worked, could someone explain the reason behind it? Thanks

Rei
  • 1
  • `res.append(path)` appends a reference to `path`, so every value in `res` becomes the same. `res.append(path[:])` appends a (shallow) copy of `path`, so each value is the same as the current value of `path`. – Nick Sep 26 '22 at 00:39
  • Does this answer your question? [List of lists changes reflected across sublists unexpectedly](https://stackoverflow.com/questions/240178/list-of-lists-changes-reflected-across-sublists-unexpectedly) – Nick Sep 26 '22 at 00:40

0 Answers0