Найти высоту дерева, где у входного дерева может быть любое количество детей

Question

Часть моей проблемы - написать функцию, которая определяет высоту дерева.

Это моя текущая функция,

def tree_height(node): 
  parent, children = node
  max_height = 0
  for child in children:
    height = tree_height(child)
    if height > max_height:
      max_height = height
  return max_height 

, но она возвращает только 0.

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

Для,

tree = ("supercalifragilisticexpialidocious",(("a",(("b",(("candy",()),)),("onomatopoeia",()),)),("d",(("egg",(("f",()),)),)),))

вывод должен быть,

3

Answer 1

Вы никогда не увеличите max_height, поэтому рекурсивные вызовы всегда будут возвращать 0; помните, что вы на один шаг выше своего ребенка.

def tree_height(node): 
    parent, children = node
    max_height = 0
    for child in children:
      child_height = tree_height(child)
      max_height = max(max_height, child_height +  1)
    return max_height

Вам нужно «поверить» в рекурсию: предположим, что tree_height(child) дает вам рост вашего ребенка. Тогда ваш рост - это максимальный рост всех ваших детей плюс один.

EDIT:

Еще код Pythonic:

def tree_height(node):
  parent, children = node
  return max([tree_height(child) + 1 for child in children]) if children else 0

Answer 2

Я думаю, что вы на правильном пути, но проблема в том, что вы, вероятно, не понимаете рекурсию height = tree_height(child), потому что, если у нее нет дочерних элементов, она возвращает 0, что в итоге вернет 0 (что является вашим случаем)

Что вы должны сделать, это поместить в функцию еще один параметр, который будет считать глубину

def tree_height(node, counter): 
    parent, children = node
    max_height = 0
    for child in children:
        height = tree_height(child, counter + 1)
        if height > max_height:
            max_height = height
    if max_height == 0:
        return counter
    return max_height

попробуйте этот код и в следующий раз напишите / нарисуйте его на бумаге, чтобы увидеть, что он делает на самом деле + не публикуйте здесь свои алгоритмические домашние задания:)