python指针在递归函数中不改变

Question

这就是我要解决的问题。然而，我无法弄清楚为什么ans的指针在递归函数中改变，但在主函数中仍然是相同的。谁能指出问题在哪里?

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

此外，我已经尝试改变返回ans返回ans.right，它的工作。还是不明白为什么上面那个不行

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

Answer 1

因为内部函数中的ans是内部函数的局部。您需要在两个函数中使用成员变量(self.ans)或将其设置为全局变量。

Answer 2

比较以下三个例子:

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

只有最后一个按你想要的方式工作。默认情况下，Python变量作用域是局部的，你需要通过nonlocal声明显式地告诉它在封闭作用域内查找，否则你将定义一个新的局部变量。

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

所以这应该可以工作:

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

注释中讨论的另一个例子:

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}

这里我们可以看到nonlocal声明是不需要的…对于属性或项访问，Python似乎将查找封闭作用域以查找实例。