LeetCode #590: Обход N-арного дерева в обратном порядке

Проблема

Для n-арного дерева вернуть постпорядок обход значений его узлов.

Например, для дерева 3-ary:

Верните его обход в обратном порядке как: [5,6,3,2,4,1].

Примечание. Рекурсивное решение тривиально. Не могли бы вы сделать это итеративно?

Решение — рекурсия

Как описывает проблема, это тривиально.

Сложность

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

Самый глубокий размер стека вызовов будет достигать самой глубокой длины пути в этом дереве. Следовательно, его пространственная сложность будет O(h), если h обозначает длину самого глубокого пути от корня до листа в этом дереве. Или это может быть O(logn), потому что h ограничено logn.

Решение — итерация

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

Сложность

Каждый узел будет посещен один раз, поэтому его временная сложность составляет O(n), если n означает количество узлов в этом дереве.

Для пространственной сложности этот стек должен иметь возможность хранить все узлы с их братьями и сестрами, размер которых не превышает N-1 в самом глубоком пути этого дерева. Таким образом, он использует O(h) дополнительного пространства, если h обозначает длину самого глубокого пути от корня до листа этого дерева. Или это может быть O(logn), потому что h ограничено logn.

См. также:  ReflexJS для внешнего интерфейса
Понравилась статья? Поделиться с друзьями:
IT Шеф
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: