Блог

Главная - Вопросы по программированию - Найти самый длинный путь четного значения в двоичном дереве, возвращаемая длина указанного пути, нерекурсивный

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

#algorithm #data-structures #binary-tree

#алгоритм #структуры данных #двоичное дерево

Вопрос:

Я должен создать алгоритм, чтобы найти самый длинный путь четного значения в двоичном дереве без использования рекурсии. Например, если мое дерево выглядит следующим образом: Двоичное дерево

Алгоритм должен возвращать 3 , поскольку это длина самого длинного пути только с четным значением.

Требования:

  • У нас есть две очереди, которые мы можем использовать
  • Путь должен начинаться с корня (который нам дан)

Что я имею в виду на данный момент:

  • Используется Morris Traversal для перехода по дереву, но я не знаю, в какой части кода выполнять часть «поиск по пути»
  • Каким-то образом используйте очереди для сохранения соответствующих узлов, q1 чтобы представлять tempLongestPath и другой, который overallLongestPath.

Но у меня нет четкого представления о том, как сохранить длину пути при переходе по дереву.

Заранее спасибо за помощь!

Комментарии:

1. разве ответ не должен быть 4 (4->8->2->10->4)

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

3. Для обхода Морриса вам необходимо изменить дерево, которое может нарушить путь решения.

Ответ №1:

Запустите BFS, представьте, что в дереве есть только четные значения, и отслеживайте длину.

Псевдокод:

 queue.put(root)
L[root] = 1
Max_L = -1
while !Queue.empty():
   current = queue.pull()
   if (current %2 ==1): SKIP/CONTINUE

   if Max_L < L[current]:
       Max_L = L[current]
   if current.left:
      queue.put(current.left)
      L[current.left] = L[current] 1
   if current.right:
      queue.put(current.right)
      L[current.right] = L[current] 1
return Max_L

Если вы не хотите использовать массив или что-то разумное (например, словарь) для хранения длин, вы можете использовать вторую очередь для их отслеживания (вместо присвоения L выполняйте put вместо присваивания L и выполняйте pull при извлечении из queue )

Комментарии:

1. Прежде всего, спасибо, что нашли время для ответа; Я ценю это. Я просто хотел уточнить, что L относится к и к чему Max_L относится.

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

3. Предполагая, что мы хотим использовать queue для хранения длины пути, какие изменения будут внесены в псевдокод? Одним из ограничений является то, что мне нужно использовать constant memory, , и я думаю L , что решение сделало бы его динамической памятью. Как бы работала эта часть, если бы это был queue : if Max_L < L[current]:

4. вы можете использовать вторую очередь вместо L сохранения текущей длины. Например, вместо L[root] = 1 того, чтобы вы можете писать queue_L.put(1) , а вместо использования L[current] вы можете делать current_len = queue_L.pull() , а затем использовать current_len для сравнения, например if Max_L < current_len: , при обновлении L[current.left] = L[current] 1 , которое вы можете делать queue_L.put(current_len 1) .

5. и что заставило вас думать, что очередь не требует динамической памяти?

Метки: , ,