Распечатать список листьев дерева с помощью рекурсии

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)

Answer 2

Это не работает, потому что если вы оставили лист, то вы вообще не смотрите на правый лист. Попробуйте это

def fringe(root):
    result = []
    if root.left:
        result.extend(fringe(root.left))
    if root.right:
        result.extend(fringe(root.right))
    if not result:
        result = [root.key]
    return result