Рекурсивная функция python возвращает узлы без дочерних элементов в дереве

Обратите внимание, что в вашем базовом случае вы возвращаете один узел. Затем этот узел распространяется обратно в рекурсии и в конечном итоге возвращается. Т.е. узел, который вам возвращается, является первым без дочерних узлов, с которыми вы столкнулись. Есть несколько способов решить эту проблему (например, путем возврата и объединения списков), но я думаю, что естественный способ сделать это - сделать вашу функцию генератором. Для этого просто замените return на yield. Затем возвращаемое значение функции функционирует как итератор, при этом каждая итерация дает следующее значение, которое будет «возвращено» при выполнении, пока функция не завершится.

Вы не предоставили мне достаточно кода, чтобы создать работоспособный и тестируемый пример, но вот мое предположение о том, что вы ищете:

def find(self):
    if not hasattr(self, 'children'):
        return [self]

    nodes = []

    for child in self.children:
        return nodes.extend(child.find())

    return nodes

# ...

nodes = root.find()
print(nodes)

Это пример ввода:

     0
   /   \
  1     2
 / \   /|\
3   4 5 6 7

Подумайте, что вы хотите, чтобы (рекурсивная) функция возвращала для каждого из узлов:

• при вызове в корне (0) он должен возвращать полный результат (3, 4, 5, 6, 7)
• при вызове на листовом узле (например, 5) он должен вернуть этот узел (5)
• для любого другого узла (например, 1) он работает так, как если бы он был корневым узлом меньшего дерева

Таким образом, иногда он возвращает один результат, а иногда и несколько. Ошибка в вашем коде здесь, потому что функция заканчивается при первом возврате, она не возвращает много:

    for i in self.children:
        return i.find2()

Есть два решения:

• сделать функцию генератора, или
• создать функцию, которая возвращает список (пусть она всегда будет возвращать список, даже если в нем всего один элемент!)

Итак, вариант 1:

def find(self):
    if not hasattr(self, 'children'): 
        yield self
    else:
        for child in self.children:
            yield from child.find()

вариант 2:

def find(self):
    if not hasattr(self, 'children'): 
        return [self]
    else:
        rtn = []
        for child in self.children:
            for result in child.find():
                rtn.append(result)
        return rtn

Я предпочитаю генератор. Кроме того, мне не особенно нравится тот факт, что некоторые из ваших узлов имеют атрибут children, а другие нет. Я бы удостоверился, что у всех из них есть children, который может быть пустым или непустым. Затем код становится:

def find_leaves(self):
    if self.children:
        for child in self.children:
            yield from child.find_leaves()
    else:
        yield self