1

我正在尝试在 python 中编写一个算法来打印从（二叉树）根到每个叶子的所有路径。这是我的代码：

def fb_problem(node, curr_trav):
    curr_trav = curr_trav + [node]

    if node.left is None and node.right is None:
        for path_node in curr_trav:
            print path_node.data 
        print "XXX"

    if node.left is not None:
        fb_problem(node.left, curr_trav)
    if node.right is not None:
        fb_problem(node.right, curr_trav)

fb_problem(root, [])

我在当前遍历中保留了一个节点列表，当我到达一个叶子时，我打印出这个列表。不过，我对 python 传递对象的方式有一些误解。我认为随着每个递归调用完成并从堆栈中弹出，原始curr_trav变量不会受到递归调用所做的事情的影响。但是，似乎这条线

curr_trav += [node]

正在改变原始列表。+=运算符返回一个新列表，而不是，.append()它实际上改变了原始对象。那么这个调用不应该只是重新分配给函数中对象的名称，而不是改变原始对象吗？当我将线路更改为类似

t_trav = curr_trav += [node]

一切正常，但我不明白原行的问题是什么。如果我的问题不清楚，请告诉我。

4

2 回答 2

4

对于 python，它既不是值也不是引用。它是两者的结合，取决于传递给函数的对象的类型。例如，如果传入一个可变类型，例如，dict, list etc它将传递引用。而对于像 a 这样的不可变类型，str它将是按值。Jeff Knupp对这个主题进行了很好的阅读。

您的原始代码的问题curr_trav += [node]在于它正在添加[node]to的值curr_trav并设置对新列表的引用。因为它传递了引用，curr_trav所以它将在每次后续迭代中更改。

于 2016-03-31T19:01:50.523 回答
1

你的理解+=不太正确。Python 中的所有运算符实际上只是快捷方式。例如，a + b如果a.__add__(b)有a一个__add__方法。如果a没有，它是b.__radd__(a)。如果b没有该方法，则会引发错误。通常，a += b行为很像a = a + b，但在可变对象的情况下，它通常不会。那是因为a += b是a.__iadd__(b)ifa有__iadd__方法。如果a没有，则与 相同a = a.__add__(b)。如果a也没有，则与a = b.__radd__(a). 由于列表确实具有该__iadd__方法，因此实际列表对象被更改而不是重新定义curr_trav。

于 2016-03-31T19:18:44.090 回答