Python 从递归 DFS 返回一个元素

Question

这涉及到 Python 如何根据对象是否不可变来通过引用传递或通过值传递。我可以递归地遍历二叉树并打印出所有值，但如果我想返回特定元素，那就有点困难了。在下面的代码中，如果节点的数据属性与传入的整数匹配，我(两次)尝试返回节点。n1 和 n2 是那些 int 值。

def get_node(self, d, root, n=[]):
    if (root == None):
        return
    else:
        if(root.data == d):
            n.append(root)
        self.get_node(d,root.left)
        self.get_node(d, root.right)
        return n



def tree_traversal(self, n1, n2):
    n1 = self.get_node(n1,self.root)[0]
    n2 = self.get_node(n2,self.root)[1]
    print(n1.data)
    print(n2.data)
    return self.helper(n1,n2)

这有效，我得到一个包含我正在查找的节点对象的列表。但是，如果我不返回(并作为参数传递)列表，而是使用字符串或 None 对象以便稍后更改，则这是行不通的。我认为这是因为列表是可变的，而字符串则不是。更重要的是，你会看到我必须将 n[1] 分配给 n2，因为由于某种原因，即使退出 get_node 递归调用并对 n2 重新执行一遍之后，返回的列表仍然在第 0 个索引中包含 n1。

有人可以解释一下为什么在分配给 n2 时列表仍然被修改吗？有没有一种方法可以代替作为参数传递并返回空列表 n，作为参数传递并返回具有默认值 None 的常规对象？

Answer 1

您的第一个问题是:

def get_node(self, d, root, n=[]):

有很多关于不要像您那样使用可变数据来默认参数的警告。我们在这里讨论的不是按引用传递，也不是按值传递(Python仅按值传递——它按值传递指向容器的指针——按引用传递是某种东西)这里的问题是默认值仅计算一次，因此所有后续调用将使用相同 结构。这就是为什么你:

have to assign n[1] to n2 because for some reason, even after exiting the get_node recursive call and doing it all over again for n2, the returned list still contains n1 in the 0th index

现在你知道原因了。这与在递归期间使用全局存储结果几乎相同。避免它。

你的函数似乎没有设计正确。如果我们正在处理一棵树，那么我们应该能够在树中的任何点执行 get_node() 或 tree_traversal() ，不应该有固定的 root 在代码中。此外，使 n1 和 n2 在同一函数中具有不同的类型和含义会令人困惑 - 使用不同的变量名称。让我们试试这样:

class Node():
    def __init__(self, data, left=None, right=None):

        assert (data is not None), "Error in tree/model logic!"

        self.data = data
        self.left = left
        self.right = right

    def get_node(self, d):

        if self.data == d:
            return self

        if self.left is not None:
            result = self.left.get_node(d)
            if result is not None:
                return result

        if self.right is not None:
            result = self.right.get_node(d)
            if result is not None:
                return result

        return None

    def tree_traversal(self, n1, n2):
        node1 = self.get_node(n1)
        node2 = self.get_node(n2)

        return node1, node2

root = Node(0)
root.left = Node(1, Node(2), Node(3, Node(4)))
root.right = Node(5, Node(6), Node(7, Node(8), Node(9)))

print(root.tree_traversal(3, 9))

现在，让我们讨论一下这是否适合您的模型。