Недвоичная высота дерева (оптимизация)

Question

Введение

Итак, я делаю курс по edX и работаю над этим практическим заданием для лучшая часть 3 часа, но я до сих пор не могу найти способ реализовать этот метод без долгого времени и тайм-аута автогрейдера.

Я пробовал 3 разных метода, каждый из которых делал одно и то же. Включая 2 рекурсивных подхода и 1 нерекурсивный подход (мой последний).

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

Формат ввода и вывода

В первой строке вводится N, равное размеру списка, указанного в строке 2.

Пример:

5
-1 0 4 0 3

Чтобы построить дерево из этого : Каждое из значений в массиве является указателем на другой индекс в массиве, так что в приведенном выше примере 0 является дочерним узлом -1 (индекс 0). Поскольку -1 указывает на отсутствие другого индекса, это корневой узел.

Дерево в примере имеет корневой узел -1, который имеет двух дочерних элементов 0 (индекс 1) и 0 (индекс 3). 0 с индексом 1 не имеет дочерних элементов, а 0 с индексом 3 имеет 1 дочерний элемент: 3 (индекс 4), у которого, в свою очередь, есть только один дочерний элемент, равный 4 (индекс 2).

Выходные данные, полученные в результате указанного выше ввода, равны 4. Это потому, что максимальная высота ветви, которая включала -1 (корневой узел), 0, 3 и 4, была высоты 4 по сравнению с высотой другой ветви. (-1 и 0), который был высотой 2.

Если вам нужно более подробное объяснение, я могу привести еще один пример в комментариях!

Выход - максимальная высота дерева. Размер входного сигнала увеличивается до 100 000 , где у меня возникли проблемы, поскольку он должен был это сделать за ровно за 3 секунды или до .

Мой код

Вот мой последний нерекурсивный метод, который я считаю самым быстрым из всех, что я сделал (все еще недостаточно быстро). Я использовал стартер с веб-сайта, который я также включу в свой код. В любом случае, спасибо за помощь!

Мой код:

# python3

import sys, threading
sys.setrecursionlimit(10**7) # max depth of recursion
threading.stack_size(2**27)  # new thread will get stack of such size

def height(node, parent_list):
        h = 0
        while not node == -1:
                h = h + 1
                node = parent_list[node]
        return h + 1

def search_bottom_nodes(parent_list):
        bottom_nodes = []
        for index, value in enumerate(parent_list):
                children = [i for i, x in enumerate(parent_list) if x == index]
                if len(children) == 0:
                        bottom_nodes.append(value)

        return bottom_nodes

class TreeHeight:
        def read(self):
                self.n = int(sys.stdin.readline())
                self.parent = list(map(int, sys.stdin.readline().split()))

        def compute_height(self):
                # Replace this code with a faster implementation
                bottom_nodes = search_bottom_nodes(self.parent)
                h = 0
                for index, value in enumerate(bottom_nodes):
                        h = max(height(value, self.parent), h)
                return h


def main():
  tree = TreeHeight()
  tree.read()
  print(tree.compute_height())

threading.Thread(target=main).start()

edX стартер:

# python3

import sys, threading
sys.setrecursionlimit(10**7) # max depth of recursion
threading.stack_size(2**27)  # new thread will get stack of such size

class TreeHeight:
        def read(self):
                self.n = int(sys.stdin.readline())
                self.parent = list(map(int, sys.stdin.readline().split()))

        def compute_height(self):
                # Replace this code with a faster implementation
                maxHeight = 0
                for vertex in range(self.n):
                        height = 0
                        i = vertex
                        while i != -1:
                                height += 1
                                i = self.parent[i]
                        maxHeight = max(maxHeight, height);
                return maxHeight;

def main():
  tree = TreeHeight()
  tree.read()
  print(tree.compute_height())

threading.Thread(target=main).start()

Answer 1

Просто кэшируйте ранее вычисленные высоты узлов, через которые вы проходили, в dict и используйте их повторно, когда на них ссылаются как на родителей.

import sys, threading
sys.setrecursionlimit(10**7) # max depth of recursion
threading.stack_size(2**27)  # new thread will get stack of such size

class TreeHeight:
    def height(self, node):
        if node == -1:
            return 0
        if self.parent[node] in self.heights:
            self.heights[node] = self.heights[self.parent[node]] + 1
        else:
            self.heights[node] = self.height(self.parent[node]) + 1
        return self.heights[node]

    def read(self):
        self.n = int(sys.stdin.readline())
        self.parent = list(map(int, sys.stdin.readline().split()))
        self.heights = {}

    def compute_height(self):
        maxHeight = 0
        for vertex in range(self.n):
            maxHeight = max(maxHeight, self.height(vertex))
        return maxHeight;

def main():
    tree = TreeHeight()
    tree.read()
    print(tree.compute_height())

threading.Thread(target=main).start()

С учетом того же ввода из вашего вопроса, это (и ваш оригинальный код) выводит:

4