leaves_and_internals 函数

Question

这个问题是学校作业，所以我不想要代码，只想要个思路。我需要写一个函数，返回两个列表，一个是树叶的列表，另一个是内部节点的列表。我的算法是：

1) 如果左子树和右子树都是空的，那就是一个树叶，我就把它加到树叶列表里。

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)

更新：

由于提问者提到他不能改变方法的签名，也不能使用实例变量，我想到一个替代方案，可以将叶子节点和内部节点返回给调用者。顺便说一下，我假设你树中的某些节点可以同时有左子节点和右子节点，所以你需要检查这两种情况（也就是说，使用两个单独的 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