Skip to content
Advertisement

Why does “temp” in this piece of code keep the value from the left side when doing right side?

# 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.

User contributions licensed under: CC BY-SA
1 People found this is helpful
Advertisement