Поиск высоты дерева без использования списка

Question

def height(t): 
''' (Tree) -> int 

Return 1 + the number of nodes in longest path in Tree t. 

>>> tree = Tree(23) 
>>> height(Tree) 
1 
>>> tree = descendents_from_list(Tree(11), [2, 3, 4, 5, 6], 3) 
>>> height(tree) 
3 
''' 
num = 1 
for i in t.children: 
    if i.children: 
     num += height(i) 
return num 

Для вышеуказанной функции с t.value и t.children мне нужно выяснить, как найти высоту БЕЗ использования списка. Как будто мне нужно найти способ рекурсивно идти дальше по дереву, не отслеживая родительские деревья.

Я пробовал, но не могу понять. Может кто-то, пожалуйста, помогите мне с этим?

Answer 1

Основная идея заключается в том, что высота дерева определяется самым длинным путем в дереве. Итак, если мы смотрим на узел с дочерними узлами, любой узел, на какой размер дочернего узла мы хотим обратить внимание? Детский узел с высотой высоты, правильно? В Python мы можем получить максимальное значение любого итеративного набора значений, используя встроенную функцию max. В каждой точке пути мы хотим добавить 1 к максимальной высоте среди всех дочерних поддеревьев.

Итак, теперь нам нужен базовый регистр для рекурсии, то есть что мы делаем, если у узла нет детей? Просто вернуться 1.

Следующий код иллюстрирует этот алгоритм:

def height(t): 
    if not t.children: 
     return 1 
    else: 
     return max(height(c) for c in t.children) + 1 

Answer 2

Вы можете создать функцию для этого, как

num = 1 
def height(t): 
    global num 
    child = [i for i in t if i.children] 
    if child: 
     num += 1 
     height(child) #reccursing 
    else: 
     return num