# 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, targetSum: int) -> List[List[int]]: self.resultpath = [] def dfs(node,target,temp): if node is None: return temp.append(node.val) print(temp) if node.left is None and node.right is None and target == node.val: self.resultpath.append(temp) dfs(node.left, target-node.val, temp) dfs(node.right, target-node.val, temp) dfs(root, targetSum, []) return self.resultpath
this is really confusing me. For a “Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22” picture of the tree: https://imgur.com/a/cAK8kQn
As this code goes through the recursions, at temp = [5,4,11], dfs(node.left …) will turn this into [5,4,11,7] but temp is still [5,4,11], so dfs(node.right …) should turn this into [5,4,11,2] but the 7 from dfs(node.left …) shows up to make it [5,4,11,7,2].
Why is that? How would I fix this code so it doesn’t do that?
Advertisement
Answer
The issue is quite simple. There is only a single temp
. You are passing a reference to this single object in all recursive calls, so any mutations in a recursive call to dfs
will be visible from the calling scope.
The key is to simply copy temp
every time you make a recursive call.