Вычислить высоту произвольного (недвоичного) дерева

Question

В настоящее время я прохожу онлайн-курс по структурам данных, и это одно из домашних заданий; пожалуйста, направляй меня к ответу, а не давай ответ.

Подсказка выглядит следующим образом:

Задание. Вам дано описание корневого дерева. Ваша задача - вычислить и вывести его высоту. Напомним, что высота (корневого) дерева - это максимальная глубина узла или максимальное расстояние от листа до корня. Вам дано произвольное дерево, не обязательно двоичное дерево.

Формат ввода. Первая строка содержит количество узлов n . Вторая строка содержит целые числа от −1 до n − 1 родителей узлов. Если i -й один из них (0 ≤ i ≤ n-1) равен -1, узел i является корнем, в противном случае он основан на 0 индекс родителя i -го узла. Гарантируется, что существует ровно один корень. Гарантируется, что вход представляет дерево.

Ограничения. 1 ≤ n ≤ 10 ⁵ .

Мое текущее решение работает, но очень медленно, когда n> 10 ² . Вот мой код:

# python3

import sys
import threading

# In Python, the default limit on recursion depth is rather low,
# so raise it here for this problem. Note that to take advantage
# of bigger stack, we have to launch the computation in a new thread.
sys.setrecursionlimit(10**7)  # max depth of recursion
threading.stack_size(2**27)   # new thread will get stack of such size
threading.Thread(target=main).start()

# returns all indices of item in seq
def listOfDupes(seq, item):
    start = -1
    locs = []
    while True:
        try:
            loc = seq.index(item, start+1)
        except:
            break
        else:
            locs.append(loc)
            start = loc
    return locs

def compute_height(node, parents):
    if node not in parents:
        return 1
    else:
        return 1 + max(compute_height(i, parents) for i in listOfDupes(parents, node))

def main():
    n = int(input())
    parents = list(map(int, input().split()))
    print(compute_height(parents.index(-1), parents))

Пример ввода:
>>> 5
>>> 4 -1 4 1 1
Это даст решение 3, потому что корень является 1, 3 и 4 ответвлением от 1, затем 0 и 2 ответвлением от 4, что дает это дерево высота 3.

Как я могу улучшить этот код, чтобы получить его с эталоном времени 3 секунды? Кроме того, было бы легче на другом языке?

Answer 1

Ваш алгоритм тратит лот времени на поиск ввода чисел. Если вы просто перебираете ввод один раз, вы можете записывать местоположения каждого числа по мере их появления, чтобы вам не приходилось продолжать поиск снова и снова. Подумайте, какая структура данных будет эффективной для записи этой информации.

Answer 2

Python будет в порядке, если вы правильно понимаете алгоритм. Так как вы ищете только руководство, подумайте:

1) Мы знаем глубину узла, если известна глубина его родителя; а также 2) Нас не интересует структура дерева, поэтому мы можем выбросить ненужную информацию.

Указатель корневого узла имеет значение -1. Предположим, мы заменили указатели его детей на корневой узел значением -2, указатели их детей - на -3 и так далее. Наибольшая абсолютная величина из них - высота дерева.

Если мы проходим по дереву от произвольного узла N (0), мы можем остановиться, как только мы встретим отрицательное значение в узле N (k), после чего мы можем заменить каждый узел значением его родителя, меньше один. Т.е., N (k-1) = N (k) -1, N (k-2) = N (k-1) - 1 ... N (0) = N (1) -1. По мере того, как все больше и больше указателей заменяются их глубиной, каждый обход, скорее всего, завершится при обнаружении узла, глубина которого уже известна. На самом деле этот алгоритм занимает в основном линейное время.

Итак: загрузите ваши данные в массив, начните с первого элемента и перемещайтесь по указателям, пока не встретите отрицательное значение. Создайте другой массив узлов, пройденных по ходу. Когда вы встретите отрицательное значение, используйте второй массив, чтобы заменить исходные значения в первом массиве их глубиной. Сделайте то же самое со вторым элементом и так далее. Следите за наибольшей глубиной, с которой вы столкнулись: это ваш ответ.

Answer 3

Структура этого вопроса выглядит так, как будто его лучше решать снизу вверх, а не сверху вниз. Ваш нисходящий подход тратит время на поиск, который не нужен, например ::

def height(tree):
    for n in tree:
        l = 1
        while n != -1:
            l += 1
            n = tree[n]
        yield l

In []:
tree = '4 -1 4 1 1'
max(height(list(map(int, tree.split()))))

Out[]:
3

Или, если вам не нравится генератор:

def height(tree):
    d = [1]*len(tree)
    for i, n in enumerate(tree):
        while n != -1:
            d[i] += 1
            n = tree[n]
    return max(d)

In []:
tree = '4 -1 4 1 1'
height(list(map(int, tree.split())))

Out[]:
3

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