python pointer is not changed in recursive function-CodePudding

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

CodePudding user response：

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.

CodePudding user response：

Compare these three examples:

In [32]: def outer():
    ...:     def inner():
    ...:         val = 3
    ...:         print(f"inner val: {val}")
    ...:     val = 0
    ...:     print(f"outer1 val: {val}")
    ...:     inner()
    ...:     print(f"outer2 val: {val}")
    ...:

In [33]: outer()
outer1 val: 0
inner val: 3
outer2 val: 0

In [34]: def outer():
    ...:     val = 0
    ...:     def inner():
    ...:         val = 3
    ...:         print(f"inner val: {val}")
    ...:
    ...:     print(f"outer1 val: {val}")
    ...:     inner()
    ...:     print(f"outer2 val: {val}")
    ...:

In [35]: outer()
outer1 val: 0
inner val: 3
outer2 val: 0

In [36]: def outer():
    ...:     def inner():
    ...:         nonlocal val
    ...:         val = 3
    ...:         print(f"inner val: {val}")
    ...:     val = 0
    ...:     print(f"outer1 val: {val}")
    ...:     inner()
    ...:     print(f"outer2 val: {val}")
    ...:

In [37]: outer()
outer1 val: 0
inner val: 3
outer2 val: 3

Only the last one works the way you want it to. Python variable scope is local by default, you need to explicitly tell it to look in the enclosing scope via the nonlocal declaration, otherwise you are defining a new variable local to the inner function.

See https://www.educative.io/edpresso/the-legb-rule-in-python

So this should work:

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        # the helper dfs function
        def dfs(root):
            nonlocal ans
            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

Another example as discussed in the comments:

In [44]: def outer():
    ...:     def inner():
    ...:         val["a"] = 3
    ...:         print(f"inner val: {val}")
    ...:     val = {"a": 1}
    ...:     print(f"outer1 val: {val}")
    ...:     inner()
    ...:     print(f"outer2 val: {val}")
    ...:

In [45]: outer()
outer1 val: {'a': 1}
inner val: {'a': 3}
outer2 val: {'a': 3}

Here we can see that nonlocal declaration is not needed... for attribute or item access it seems that Python will look to the enclosing scope to find the instance.