Python return 来自递归 DFS 的元素

Question

这与 Python 如何通过引用传递或通过值传递有关，具体取决于对象是否不可变。我能够递归地遍历二叉树并打印出所有值，但是如果我想 return 一个特定的元素，那就有点困难了。在下面的代码中，如果节点的数据属性与传入的整数匹配，我（两次）尝试 return 一个节点。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)

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

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

Answer 1

你的第一个问题是：

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

有很多关于不要像您那样使用可变数据来默认参数的警告。我们这里不是在讨论按引用传递也不是按值传递（Python 仅通过 value 传递——它传递指向按值容器——按引用传递完全是另一回事。）这里的问题是默认值只被评估一次，所以 all 随后调用将使用 相同的 structure.That 你的原因：

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))

现在，让我们讨论一下这如何适合或不适合您的模型。

Python return 来自递归 DFS 的元素

Python return an element from recursive DFS

python

recursion

binary-tree

python-3.x