Подсчет всех узлов всех путей от корня до листьев

Question

Если дано дерево с узлами с целыми числами: 1 ~ 10 и коэффициентом ветвления 3 для всех узлов, как я могу написать функцию, которая проходит через дерево, считая от корня до листьев для КАЖДОГО пути?

Итак, для этого примера, скажем, нужно вернуть это:

{1: 1, 2: 5}

Я пробовал эту вспомогательную функцию:

def tree_lengths(t):
    temp = []
    for i in t.children:
        temp.append(1)
        temp += [e + 1 for e in tree_lengths(i)]
    return temp

Слишком много ошибок с этим кодом. С одной стороны, он оставляет отпечатки каждого посещенного узла в обходе в возвращаемом списке - поэтому трудно определить, какие значения мне нужны из этого списка. С другой стороны, если дерево большое, оно не оставляет отпечатков корневого и более ранних узлов в пути до достижения строки "для i в t.children". Для этого нужно сначала: продублировать все пути от корневых листьев; второе: вернуть список исключительно для конечного числа каждого пути.

Пожалуйста помоги! Это так сложно.

Answer 1

Я не совсем уверен, что именно вы пытаетесь сделать, но вам, вероятно, потребуется определить рекурсивную функцию, которая принимает узел (верхушка дерева или поддерева) и целое число (количество дочерних элементов, которые вы пересекали, так что далеко), и, возможно, список каждого посещенного узла до сих пор. Если у узла нет дочерних элементов, вы достигли листа и можете распечатать любую информацию, которая вам нужна. В противном случае для каждого дочернего элемента вызовите эту рекурсивную функцию еще раз с новыми параметрами (+1 к числу, дочерний узел в качестве главного узла и т. Д.).