Обход порядка уровней N-арного дерева

Опубликовано: 19 Сентября, 2022

Дано N-арное дерево. Задача состоит в том, чтобы напечатать обход дерева по порядку уровней, где каждый уровень будет в новой строке.

Примеры:

Input:

Image

Output: 
1
3 2 4
5 6
Explanation: At level 1: only 1 is present.
At level 2: 3, 2, 4 is present
At level 3: 5, 6 is present

Input:

Image

Output:  
1
2 3 4 5
6 7 8 9 10
11 12 13
14
Explanation: For the above example there are 5 level present in the n-ary tree.
At level 1: only 1 is present.
At level 2: 2, 3, 4, 5 is present.
At level 3: 6, 7, 8, 9, 10 is present
At level 4:11, 12, 13 is present
At level 5 :- 14 is present

Подход 1: Использование BFS

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

Для реализации подхода выполните следующие шаги:

  • Создайте вектор ans и temp для хранения обхода порядка уровней N-арного дерева.
  • Вставьте корневой узел в очередь.
  • Запустите цикл while, пока очередь не станет пустой:
    • Определите размер текущего уровня, который является размером очереди (скажем, N ):
      • Запустите цикл для i = 1 до N
      • На каждом шаге удаляйте передний узел (скажем, cur ) и передавайте его данные во временный файл как часть текущего уровня.
      • Поместите всех потомков cur в очередь.
    • Вставьте temp в окончательный вектор ans , который хранит разные уровни в разных строках.
  • Верните вектор ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(V), где V — количество узлов.
Вспомогательное пространство: O(V)

Подход 2: Использование DFS

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

  • Функция LevelOrder обновит an с текущим значением, вставив его в новый подвектор, если тот, который соответствует уровню, еще не присутствует в an.
  • Функция повысит уровень на 1;
  • Он будет вызывать себя рекурсивно для всех дочерних элементов;
  • Это откатится на уровень.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(V)
Вспомогательное пространство: O(V)

РЕКОМЕНДУЕМЫЕ СТАТЬИ