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中，如果将mutable object传递给函数/方法，则该函数/方法将获得对该对象的引用。因此，只要您仍然将其视为同一个可变对象(即，不直接将参数与其他对象一起赋值)，您对该对象所做的任何更改对调用者也是可见的。由于list是一个mutable type，因此此行为对您感兴趣的情况非常有帮助。

并确保在从外部调用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提到他不能更改方法的签名，也不能使用实例变量，这是我能想到的另一种解决方案，它将叶子和内部返回给调用者。顺便说一句，我假设你的树中的一些节点可以同时具有左和右，所以你需要同时检查两个节点(即使用两个单独的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