Python递归DFS返回指定节点问题及可变对象传参疑问

你遇到的核心问题是Python默认参数的创建时机——函数的默认参数是在函数定义的时候就初始化了，而不是每次调用函数时重新创建。列表是可变对象，所以当你第一次调用get_node时，修改了这个默认的列表n，它的状态会被保留下来；第二次调用时，函数会复用这个已经被修改过的列表，新找到的节点会直接追加进去，导致返回的列表包含两次调用的结果。这就是为什么你第二次调用get_node时，列表里还留着第一次的n1节点，需要取索引1来获取n2。

至于用字符串或None无法生效，是因为它们属于不可变对象。在递归过程中，如果你试图给它们赋值（比如n = root），其实只是创建了一个新的局部变量，不会影响上层递归调用中的n；而列表是可变的，append操作直接修改了原对象的内容，所以能在整个递归链路中收集到所有匹配的节点。

能不能用默认值为None的普通对象替代？ #

当然可以！这还是Python中规避默认可变参数陷阱的标准做法。你可以把默认参数设为None，然后在函数内部判断，如果n是None，就初始化一个新的列表（或你需要的普通对象）。这样每次调用函数时，都会创建一个全新的空列表，不会复用之前的状态。

改进后的代码示例：

def get_node(self, d, root, n=None):
    # 每次调用时初始化新列表，彻底避免复用默认参数的对象
    if n is None:
        n = []
    if root is None:
        return
    if root.data == d:
        n.append(root)
    # 递归时传递当前的n列表
    self.get_node(d, root.left, n)
    self.get_node(d, root.right, n)
    return n

def tree_traversal(self, n1_val, n2_val):
    # 现在每次调用get_node都会返回独立的列表，直接取索引0即可
    n1 = self.get_node(n1_val, self.root)[0]
    n2 = self.get_node(n2_val, self.root)[0]
    print(n1.data)
    print(n2.data)
    return self.helper(n1, n2)

额外优化建议 #

如果你的需求是找到第一个匹配的节点就返回，而不是收集所有匹配节点，还可以简化递归逻辑，找到后直接返回，不需要遍历整个树：

def get_node(self, d, root):
    if root is None:
        return None
    if root.data == d:
        return root
    # 先遍历左子树，找到结果直接返回
    left_result = self.get_node(d, root.left)
    if left_result is not None:
        return left_result
    # 左子树没找到，再遍历右子树
    return self.get_node(d, root.right)

这样调用时直接n1 = self.get_node(n1_val, self.root)即可，不需要处理列表，效率也更高。

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