Задача 1: Обход N-арного дерева по предзаказу

Напишите определение функции preorder(root: Node) -> list[int], которая принимает корень n-арного дерева и возвращает список значений его узлов в порядке их обхода в прямом порядке (preorder traversal).

Что такое прямой порядок (preorder traversal)?

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

Описание класса Node

Для представления узлов дерева используется класс:

class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val  # Значение текущего узла
        self.children = children  # Список дочерних узлов

• Каждый узел может содержать любое количество дочерних узлов.
• Если узел является листом, его children равно None или пустому списку [].

Этот класс заранее заготовлен в коде, его изменять не нужно.

Формат ввода

Дерево передается в формате сериализации уровневого обхода (level order):

• Значения узлов указываются в порядке уровневого обхода.
• Группы дочерних узлов разделяются значением null.

Пример:

• root = [1,null,3,2,4,null,5,6] представляет следующее дерево:

          1
        / | \
       3  2  4
      / \
     5   6
  

Формат вывода

Возвращается список значений узлов в порядке их обхода preorder.

Примеры

Пример 1

Ввод:

root = [1,null,3,2,4,null,5,6]

Графическое представление дерева:

          1
        / | \
       3  2  4
      / \
     5   6

Вывод:

[1, 3, 5, 6, 2, 4]

Пример 2

Ввод:

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]

Графическое представление дерева:

                   1
         /    |    |    \
       2      3    4     5
            /  \         / \
           6    7       9  10
                |       |
                11      13
                |
                14

Вывод:

[1, 2, 3, 6, 7, 11, 14, 4, 8, 12, 5, 9, 13, 10]