Python递归函数内指针赋值不生效问题原因排查

问题现象 #

在实现「在二叉树的克隆树中找到对应目标节点」题目逻辑时，出现两种写法效果不一致的情况：

• 直接在递归函数内给ans变量赋值，主函数中ans始终为初始值，无法返回正确结果
• 修改为给ans的right属性赋值，最终返回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 = root
                return
            dfs(root.left)
            dfs(root.right)
        
        # main function
        ans = TreeNode(0)
        dfs(cloned)
        return ans

可正常运行的代码 #

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

核心原因 #

问题本质是Python的变量作用域规则导致的：

1. 第一种写法失效的原因
   Python中如果在函数内部直接对变量名执行赋值操作（比如ans = root），解释器会默认将这个变量判定为当前函数的局部变量，不会去外层作用域查找同名变量。
   上述dfs函数中执行ans = root时，实际上是在dfs的局部作用域里创建了一个叫ans的新变量，给这个局部变量赋值完全不会影响外层getTargetCopy函数中定义的ans变量，所以外层ans始终是初始的TreeNode(0)，返回结果自然错误。

2. 第二种写法生效的原因
   第二种写法中没有对ans这个变量名本身做重新赋值，执行的是ans.right = root——这是修改已有对象的属性操作。此时解释器在dfs局部作用域找不到ans变量，就会按照作用域查找规则去外层getTargetCopy的作用域找到之前初始化的ans对象，直接修改这个对象的right属性。整个过程中外层的ans对象没有被替换，只是它的属性值被更新了，所以最后返回ans.right就能拿到正确的目标节点。

可以用一个简单的类比理解：外层作用域的ans是一个贴了名字标签的盒子。第一种写法是在dfs里新拿了一个同名标签贴到新盒子上，往新盒子里放东西，原来的盒子完全没被改动；第二种写法是找到外层原来的那个盒子，打开盒子修改里面存放的内容，盒子本身还是原来的那个，所以最后能从里面拿到放进去的目标节点。

如果要修正第一种写法，只需要在dfs函数内加nonlocal ans声明，显式告诉解释器ans是外层作用域的变量，不是dfs的局部变量即可。

内容的提问来源于stack exchange，提问作者Yuan