«Учебный план LeetCode 75 для лучших интервью» — это учебный план, который предлагает график выполнения набора из 75 задач по программированию на LeetCode в течение нескольких недель с целью подготовки навыков для технических собеседований и улучшения кодирования.

589. Предварительный обход N-арного дерева

Учитывая root n-арного дерева, вернуть обход в прямом порядке значений его узлов.

Сериализация ввода Nary-Tree представлена ​​в их обходе по уровням. Каждая группа детей отделена нулевым значением (см. примеры)

Пример 1:

Ввод: root = [1,null,3,2,4,null,5,6]
Вывод: [1,3,5,6,2,4]

Пример 2:

Ввод: корень = [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,6,7,11,14,4,8,12,5,9,13,10]

Решение

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if root is None:
            return []
        result = [root.val]
        for child in root.children:
            result += self.preorder(child)
        return result

Описание решения

Данный код определяет класс Solution с методом preorder, который принимает параметр root, представляющий корневой узел n-арного дерева. Метод возвращает список значений узлов дерева в предварительном порядке.

Метод сначала проверяет, является ли корневой узел None. Если это так, он возвращает пустой список. Если корень не None, он добавляет значение корневого узла в список результатов, а затем выполняет итерацию по каждому дочернему элементу корня. Для каждого дочернего элемента он рекурсивно вызывает метод preorder для дочернего элемента и добавляет результат в список. Наконец, метод возвращает список результатов.

Этот алгоритм имеет временную сложность O(n), где n — количество узлов в дереве, потому что мы посещаем каждый узел ровно один раз. Сложность пространства также равна O(n), потому что рекурсивные вызовы используют до O(n) пространства в стеке вызовов.

102. Обход порядка уровней двоичного дерева

Учитывая root бинарного дерева, вернуть порядок обхода значений его узлов. (то есть слева направо, уровень за уровнем).

Пример 1:

Ввод: root = [3,9,20,null,null,15,7]
Вывод: [[3],[9,20],[15,7]]

Пример 2:

Ввод: root = [1]
Вывод: [[1]]

Пример 3:

Ввод: root = []
Вывод: []

Решение

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        result = []
        queue = deque([root])
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)
        return result

Описание решения

Данный код определяет класс Solution с методом levelOrder, который принимает параметр root, представляющий корневой узел двоичного дерева. Метод возвращает список списков, где каждый внутренний список представляет значения узлов на определенном уровне дерева слева направо.

Метод сначала проверяет, является ли корневой узел None. Если это так, он возвращает пустой список. Если корень не None, он инициализирует пустой список result и очередь queue, содержащую корневой узел.

Затем он входит в цикл, который продолжается до тех пор, пока очередь не станет пустой. На каждой итерации цикла он инициализирует пустой список level и удаляет первый узел из очереди. Он добавляет значение удаленного узла к level и добавляет level к result.

Если у удаленного узла есть левый дочерний элемент, он добавляется в очередь. Если у удаленного узла есть правильный дочерний узел, он добавляет его в очередь.

Наконец, метод возвращает result.

Этот алгоритм имеет временную сложность O(n), где n — количество узлов в дереве, потому что мы посещаем каждый узел ровно один раз. Сложность пространства также равна O(n), потому что очередь может хранить до O(n) узлов одновременно.