我正在尝试解决一个面试问题:如何将 BST 转换为双链表。 下面是我的代码。我真的很困惑 python 递归是如何工作的。为什么在convert2DoubleLst_recursive之后，prev和head仍然是None，我已经为这两个变量分配了新值，为什么在这个方法调用之后，我无法保存更改。我记得 python 通过引用传递参数，但为什么在这里我无法保存更改。非常感谢。
def convert2_recursive(node):
prev,head=None,None
convert2DoubleLst_recursive(node,prev,head)
end=head.lChild
printList(head,end)
def convert2DoubleLst_recursive(node,prev,head):
if node:
convert2DoubleLst_recursive(node.lChild,prev,head)
node.lChild=prev
if prev:
prev.rChild=node
else:
head=node
nextNode=node.rChild
head.lChild=node
node.rChild=head
prev=node
convert2DoubleLst_recursive(nextNode,prev,head)
最佳答案
天真地说，因为Python中没有引用传递。递归不是你的问题。
当你想到“Python 中没有变量，只有名称和值”时，情况可能会变得更清晰一些。
当声明convert2DoubleLst_recursive(node.lChild, prev, head)时执行后，实际上是函数convert2DoubleLst_recursive被调用的值是 node.lChild , prev和head指向当时。
然后，在convert2DoubleLst_recursive内，这些值被赋予(本地)名称 node等等(与以前的名称不同!)。
稍后，您为这些名称分配新值，进行递归(这实际上与您的代码无关)，并且本质上 Python 在退出函数时会忘记这些名称及其值。
基本上，在第 8 行和第 10 行之间 prev不会改变它的值(正如您所经历的)，因为调用者中使用的名称在被调用者内部永远不会看到。分配给该名称的值在第 3 行中没有更改，并且与被调用者内部发生的情况无关。
如果您想将值传递回调用者，您必须 return他们。
或者您可以替换 None由一个监护对象，其行为类似于您的节点类并代表 None .
不过，通常情况下，在 Python 中可以使用比链表更好的数据结构。
(例如，Python list 内部已经是链表，可以使用它来代替。)
更深入的分析可以在这里找到:https://stackoverflow.com/a/986145/110707 .
关于python - Python 中的递归是如何工作的，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21188649/