ZigZag Level Order Обход N-арного дерева

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

Примеры:

Input:

Output:
1
3 2
4 5 6 7 8

Подход: Данная проблема может быть решена с помощью BFS Traversal. Подход очень похож на обход по порядку уровней N-арного дерева. Можно заметить, что при изменении порядка четных уровней во время обхода порядка уровней полученная последовательность является обходом зигзага. Основываясь на этих наблюдениях, ниже приведены шаги, которые необходимо выполнить:

• Во время обхода BFS сохраните узлы каждого уровня в векторе, скажем, curLevel[] .
• Для каждого соответствующего уровня сохраните curLevel в вектор векторов, скажем, result[] .
• Переверните векторы, присутствующие в четных позициях в результате[] .
• После выполнения вышеперечисленных шагов все векторы сохраняют в результате[] требуемый результат.

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

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