Задача: 590. N-ary Tree Postorder Traversal
Дано корневое дерево с n-арной структурой, верните обход дерева в постфиксном порядке для значений его узлов.
Сериализация входных данных n-арного дерева представлена в обходе уровней. Каждая группа детей разделяется значением null (см. примеры).
Пример:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]
👨💻 Алгоритм:
1⃣Инициализируйте стек для хранения узлов и список для хранения значений узлов в обратном порядке.
2⃣Начните с корневого узла и добавьте его в стек. Пока стек не пуст, извлекайте узлы из стека, добавляя их значения в начало списка, и добавляйте всех его детей в стек.
3⃣В конце верните список значений узлов.
😊 Решение:
class Solution {
public List<Integer> postorder(Node root) {
LinkedList<Node> stack = new LinkedList<>();
LinkedList<Integer> output = new LinkedList<>();
if (root == null) {
return output;
}
stack.add(root);
while (!stack.isEmpty()) {
Node node = stack.pollLast();
output.addFirst(node.val);
for (Node item : node.children) {
if (item != null) {
stack.add(item);
}
}
}
return output;
}
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
}
}👉Новости 👉Платформа