«Учебный план 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) узлов одновременно.