Задача: 589. N-ary Tree Preorder Traversal
Сложность: easy

Дан корень N-арного дерева, верните значения его узлов в порядке предварительного (preorder) обхода.
Сериализация ввода 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: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

👨‍💻 Алгоритм:

1⃣Инициализация
Создайте два списка: stack для хранения узлов и output для хранения значений узлов в порядке обхода. Добавьте корневой узел в stack.

2⃣Итеративный обход
Пока stack не пуст, извлекайте узел из stack и добавляйте его значение в output. Разверните список дочерних узлов текущего узла и добавьте их в stack.

3⃣Возврат результата
Верните список output как результат.

😎 Решение:

class Node {
    public $val;
    public $children;

    function __construct($val = 0, $children = []) {
        $this->val = $val;
        $this->children = $children;
    }
}

class Solution {
    function preorder($root) {
        if ($root === null) return [];
        $stack = [$root];
        $output = [];
        
        while (!empty($stack)) {
            $node = array_pop($stack);
            $output[] = $node->val;
            $children = array_reverse($node->children);
            foreach ($children as $child) {
                $stack[] = $child;
            }
        }
        
        return $output;
    }
}

Ставь 👍 и забирай 📚 Базу знаний