[Python] Вычислить высоту дерева

Деревья имеют огромное количество применений в Computer  Science. Они используются

как для представления данных, так и во многих алгоритмах машинного обучения. В ряде собеседований на позицию разработчика – необходимо решить задачу на нахождение высоты дерева, самым оптимальным образом. Я столкнулся с данной задачей проходя курс на сайте stepik.org (Алгоритмы: теория и практика. Структуры данных) и для меня данная задача оказалось непростой, так как я никогда не работал с данным типом структуры, задача заставила хорошенько потрудится.

К примеру, входящие данные и визуализация дерева:

0	1	2	3	4
4	-1	4	1	1

Мой пример кода для решения задачи, основывается на переборе всех листьев дерева до корня (индекс со значением -1) и подсчет максимального значения:

1.       Вариант № 1:

Рекурсивное решение задачи:

import sys

debug = False

MAX_PATH = 0

#--------------------Decorator as performance counter------------------------------

def count_perf(f):

    import datetime

    def wraper(*args, **kwargs):

        time_init = datetime.datetime.now()

        result = f(*args, **kwargs)

        time_end = datetime.datetime.now()

        total = time_end -  time_init

        print('Time: {}'.format(total))

        return result

    return wraper

#-----------------------------------------------------------------------------------

@count_perf

def CountHeight(n, array):

    global MAX_PATH

    MAX_PATH = 0

    result = array or 0

#---------------------Рекурсивная функция-----------------------------------------------

    def Height(idx, array):

        global MAX_PATH

        parent = array[idx]

        MAX_PATH += 1

        if parent != -1:

            Height(parent, array)

        return MAX_PATH

 #-------------------------------------------------------------------------------------

    def GetMax(n, array):

        global MAX_PATH

        v = 0

        MAX_HEIGHT = 0

        for index in range(n):

            tmp = Height(index, array)

            if tmp > MAX_HEIGHT:

                MAX_HEIGHT = tmp

            MAX_PATH = 0

        return MAX_HEIGHT

  

    result = GetMax(n,array) or 0

    return result

def main():

    n = int(input().strip() or 0)

    array = input().split()

    array = map(float, array)

    array = list(map(round, array))

    l = len(array)

    if l != n:

        n = l

    if l > 100:

                from sys import setrecursionlimit

                setrecursionlimit(10000)

    return CountHeight(n, array)

if __name__ == "__main__":

     print(main())

Скрипт работает очень быстро, но при вводе данных содержащих большое количество рекурсии при обходе листьев (примерно > 50 раз), программа неожиданно завершалась. Более того дебаггинг мне никак не помогал. После ручной трасировки программы, оказалось, что происходил “stack overflow” приложения python, а увеличение глубины рекурсии через функцию

sys.setrecursionlimit(10000) никак не помогало. Решением было отказаться от рекурсивного метода в пользу итеративного.

2.       Вариант № 2:

Как вариант, была идея сохранять значения уже имеющихся данных о расстоянии индексах (которые мы получили от предыдущих итерациях) в словаре:

import sys

#--------------------Decorator as performance counter-------------------------

def count_perf(f):

    import datetime

    def wraper(*args, **kwargs):

        time_init = datetime.datetime.now()

        result = f(*args, **kwargs)

        time_end = datetime.datetime.now()

        total = time_end -  time_init

        print('Time: {}'.format(total))

        return result

    return wraper

#-----------------------------------------------------------------------------------

   

@count_perf

def Height(n, tree):

    root = -1

    height = 1

    result = height

    maxpath = 0

    tmp_save = {} #Словарь содержащий уже рассчитанные значения листьев

    for node in range(n):

        parent = tree[node]

        if parent == root:

            tmp_save[node] = 1

        else:

            height += 1

            while True:

                 path = tree[parent]

                 if path != root:

                    

                     if path in tmp_save:#Если имеется уже в словаре, берем значение

                         height = height + tmp_save[path]

                         tmp_save[node] = height #Сохраняем информацию о глубине

                         if height > maxpath:

                            maxpath = height

                         height = 1

                         break

                     parent = path

                     height += 1

                 else:

                        tmp_save[node] = height #Сохраняем информацию о глубине

                        if height > maxpath:

                            maxpath = height

                        height = 1

                        break

    return maxpath

def main():

    n = int(input().strip() or 0)

    array = input().split()

    array = map(float, array)

    array = list(map(round, array))

    l = len(array)

    if l != n:

        n = l

    return  Height(n, array)

if __name__ == "__main__":

     print(main())

Оказалась, что если значение индекса совпадает с значением  родителя ([7] -> [7]) происходит бесконечный цикл, который никогда не завершится. Рекомендуется проверять данное условие.  Для примера проверки алгоритма можно воспользоватся следующими значениями ([*] Высота дерева):

9 7 5 5 2 9 9 9 4 -1 7 1 10 12 2 13 15 3 2 9 4 6 20 22 23 20 25 8 26 27 29 9 30 5 5 2 9 9 9 4 23 7 1 10 12 2 13 15 3 2 1 4 6 0 22 3 20 11 8 26 27 29 9 7 5 5 2 9 9 9 4 21 7 1 10 12 2 13 15 3 2 1 4 33 0 22 3 20 11 84 26 27 29 9 7 5 5 2 9 90 9 4 29 7 1 10 12 2 13 15 3 2 1 4 6 0 22 3 20 11 8 26 27 29 9 7 5 5 2 9 9 9 4 22 7 1 10 12

 [9] 

9 7 5 5 2 9 9 9 2 -1

[ 4] 

19 10 11 17 -1 13 10 19 1 6 4 14 2 20 5 12 15 1 17 6 10 

[11]