1

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

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

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

任何帮助是极大的赞赏。谢谢

4

1 回答 1

1

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

在 python 中，如果将 a 传递mutable object给函数/方法，则函数/方法将获得对该对象的引用。因此，只要您仍然将其视为相同的可变对象（即不直接将参数分配给其他对象），您对对象所做的任何更改对调用者也是可见的。由于list是 a 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 提到他不能更改方法的签名也不能使用实例变量，这是我能想到的另一种解决方案，它将叶子和内部返回给调用者。顺便说一句，我假设您的树中的某些节点可以同时具有左右，因此您需要同时检查两者（即使用 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
于 2013-03-08T06:01:10.507 回答