python - leaves_and_internals 函数

Question

这个问题是针对学校(家庭作业)的，所以我不要求代码，我也不想要任何代码，只是一个想法。我必须编写一个返回两个列表的函数，一个二叉树的叶子列表和一个内部节点列表。我的算法是:

1)如果左子树和右子树都是None，那么它是一个叶子，所以我将它添加到叶子列表中。

2)如果不存在，则将其添加到内部列表中，并调用左子树上的函数，然后调用右子树上的函数(如果存在)。

这是我编写的代码:

def leaves_and_internals(self):
    leaves = []
    internals = []

    if self.left is None and self.right is None:
        leaves.append(self.item)
    else:     
        internals.append(self.item)
        if self.left != None:
            leaves_and_internals(self.left)
        else:
            leaves_and_internals(self.right)
    return internals, leaves

我很确定该算法是正确的，但我认为每次我在节点上递归时，列表都会重置。我该如何解决这个问题？

非常感谢任何帮助。谢谢

Answer 1

我没有研究过你的代码的算法，只是提出了你所遇到的问题的答案。您可以将leaves 和internals 作为参数传递给递归函数，以便在递归调用中保留它们的内容。

在Python中，如果将可变对象传递给函数/方法，则函数/方法将获得对该对象的引用。因此，只要您仍然将其视为相同的可变对象(即不直接用其他东西分配参数)，您对对象所做的任何更改对调用者来说也是可见的。由于 list 是一个可变类型，因此此行为对于您感兴趣的情况非常有帮助。

并确保在从外部调用 leaves_and_internals 函数之前将列表初始化为 []。

def leaves_and_internals(self, leaves, internals):
    if self.left is None and self.right is None:
        leaves.append(self.item)
    else:
        internals.append(self.item)
        if self.left != None:
            leaves_and_internals(self.left, leaves, internals)
        else:
            leaves_and_internals(self.right, leaves, internals)
    return


 # Somewhere outside
 leaves = []
 internals = []
 myobj.leaves_and_internals(leaves, internals)

更新:

由于OP提到他不能更改方法的签名，也不能使用实例变量，所以这是我能想到的另一种解决方案，它将叶子和内部返回给调用者。顺便说一句，我假设树中的某些节点可以同时具有左侧和右侧，因此您需要检查两者(即使用 2 个单独的 if 而不是 if...else).

def leaves_and_internals(self):
    leaves = []
    internals = []
    if self.left is None and self.right is None:
        leaves = [ self.item ]
    else:
        if self.left != None:
            leaves, internals = leaves_and_internals(self.left)
        if self.right != None:
            templeaves, tempinternals = leaves_and_internals(self.right)
            leaves += templeaves
            internals += tempinternals
        internals.append(self.item)
    return leaves, internals