Проблема
Для 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.