Search code examples
pythonpointersrecursionbinary-tree

python pointer is not changed in recursive function


This is the problem that I want to solve. However, I cannot figure out why the pointer of ans is changed in recursion function but is still the same in the main function. Could anyone points out where the problem is?

https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/solution/

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        # the helper dfs function
        def dfs(root):
            if not root: return
            if root.val == target.val:
                ans = root
                return
            dfs(root.left)
            dfs(root.right)
        
        # main function
        ans = TreeNode(0)
        dfs(cloned)
        return ans

Also, I have tried changing return ans to return ans.right and it works. Still don't understand why it works but the upper one cannot work

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        # the helper dfs function
        def dfs(root):
            if not root: return
            if root.val == target.val:
                ans.right = root
                return
            dfs(root.left)
            dfs(root.right)
        
        # main function
        ans = TreeNode(0)
        dfs(cloned)
        return ans.right

Solution

  • Because ans in the inner function is local to the inner function. You will need to use a member variable (self.ans) or make it a global in both functions.