时间戳

首页 > 解决方案 > Python 从递归 DFS 返回一个元素

python - Python 从递归 DFS 返回一个元素

问题描述

这与 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的常规对象？

标签： pythonpython-3.xrecursionbinary-tree

解决方案

你的第一个问题是这样的：

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

有很多关于不使用可变数据来默认参数的警告。我们不是在讨论按引用传递或按值传递（Python仅按值传递——它按值传递指向容器的指针——按引用传递完全是另外一回事。）这里的问题是默认值只是评估一次，因此所有后续调用都将使用相同的结构。这就是为什么你：

必须将 n[1] 分配给 n2，因为出于某种原因，即使在退出 get_node 递归调用并为 n2 重新执行此操作后，返回的列表仍然在第 0 个索引中包含 n1

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

您的功能似乎设计不正确。如果我们正在使用一棵树，那么我们应该能够做到，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))

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

推荐阅读