使用递归打印树的叶子列表

Question

我需要编写一个函数，我需要在其中返回树的叶子列表。

所以对于这棵树：

        1
    2       3
 4       5     6

这应该打印 [4, 5, 6]

这是我到目前为止所想出的。我似乎无法找到如何返回该功能。它只打印 [4]

def fringe(root):

    if root.left:
        return fringe(root.left)
    elif root.right:
        return fringe(root.right)
    else:
        return [root.key]

任何输入？

Answer 1

使用yield创建发生器：

def fringe(root):

    if root.left or root.right:
        if root.left:
            for key in fringe(root.left):
                yield key
        if root.right:
            for key in fringe(root.right):
                yield key
    else:
        yield root.key

print list(fringe(mytree))

在较新版本的 python 中，而不是

for key in fringe(root.left):
    yield key

您可以使用：

yield from fringe(root.left)