0

I am trying to solve a binary tree problem Path to Given Node using Python. I am confused about how the append function does reflect on a list I passed in the recursive function, but if I try to copy a list by value it does not work.

Append function

class TreeNode:
   def __init__(self, x):
       self.val = x
       self.left = None
       self.right = None

class Solution:
    # @param A : root node of tree
    # @param B : integer
    # @return a list of integers
    
    def solve(self, A, B):
        ans = []
        self.f(A, B, [], ans)
        return ans[0]

    def f(self, node, val, cur, ans):
        if(node == None): return
        
        cur.append(node.val)

        if(node.val == val):
            ans.append(cur[:]) # Append. Does work!!!
            return 

        self.f(node.left, val, cur, ans)
        self.f(node.right, val, cur, ans)
        cur.pop()

# Sample tree
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.left = TreeNode(0)
root.left.right = TreeNode(-2)
root.right.left = TreeNode(2)

print(Solution().solve(root,-2)) # Find path from root to node -2
# I get the correct answer [3, 1, -2]

Copy by value

class TreeNode:
   def __init__(self, x):
       self.val = x
       self.left = None
       self.right = None

class Solution:
    # @param A : root node of tree
    # @param B : integer
    # @return a list of integers
    
    def solve(self, A, B):
        ans = []
        self.f(A, B, [], ans)
        return ans

    def f(self, node, val, cur, ans):
        if(node == None): return
        
        cur.append(node.val)

        if(node.val == val):
            ans = cur[:] # Copy by value. Does not work!!!
            return 

        self.f(node.left, val, cur, ans)
        self.f(node.right, val, cur, ans)
        cur.pop()

# Sample tree
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.left = TreeNode(0)
root.left.right = TreeNode(-2)
root.right.left = TreeNode(2)

print(Solution().solve(root,-2)) # Find path from root to node -2
# I get an empty list []. Was expecting [3, 1, -2]

I tried copy.deepcopy() as well, but that also does not work (I get an empty list).

martineau
  • 119,623
  • 25
  • 170
  • 301
qshahrukh40
  • 1
  • 2
  • 1
    `ans = cur[:]` just reassigns to a local variable. Python doesn't deal with variable references like C++ and PHP where you can reassign to a variable and expect the caller's variable to see that change as well. But you can mutate objects that are the underlying memory locations a variable might allow you access to. – ggorlen Jul 22 '22 at 21:26
  • Conversely, `ans[:] = cur` will mutate the existing object `ans` by copying the elements of `cur` into it. – slothrop Jul 22 '22 at 21:35

0 Answers0