Level Order, Right Side View, Min Depth.
Поиск в ширину — обход графа уровнями. Использует очередь. Находит кратчайший путь в невзвешенном графе.
BFS обходит граф/дерево уровнями: сначала все узлы на расстоянии 1, затем на расстоянии 2, и т.д.
Граф — структура из вершин (узлов) и рёбер (соединений между вершинами).
Очередь (Queue) — структура данных FIFO (First-In-First-Out).
Уровень — все узлы на одинаковом расстоянии от начального.
Кратчайший путь — путь с минимальным количеством рёбер.
from collections import deque
def bfs(start):
queue = deque([start])
visited = {start}
steps = 0
while queue:
# Обрабатываем весь уровень
for _ in range(len(queue)):
node = queue.popleft()
if is_target(node):
return steps
for neighbor in get_neighbors(node):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
steps += 1
return -1Условие: Дано бинарное дерево. Верните посимвольный обход по уровням (слева направо, уровень за уровнем).
Примеры:
Ввод: root = [3,9,20,null,null,15,7]
Вывод: [[3],[9,20],[15,7]]
Ввод: root = [1]
Вывод: [[1]]
Ввод: root = []
Вывод: []
Ограничения:
💡 Подсказка: Используйте очередь. Для обработки каждого уровня фиксируйте размер очереди перед началом итерации:
for _ in range(len(queue)).
Дерево: [3, 9, 20, null, null, 15, 7]
3 Уровень 0: [3] queue: [3]
/ \ result: [] step = 0
9 20
/ \
15 7
Шаг 1: Обработка уровня 0
queue: [3] → pop(3) → add(9, 20)
result: [[3]]
queue: [9, 20]
Шаг 2: Обработка уровня 1
queue: [9, 20] → pop(9), pop(20) → add(15, 7)
result: [[3], [9, 20]]
queue: [15, 7]
Шаг 3: Обработка уровня 2
queue: [15, 7] → pop(15), pop(7)
result: [[3], [9, 20], [15, 7]]
queue: [] ← пусто, завершаем
Решение:
from collections import deque
def levelOrder(root):
if not root:
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Объяснение:
Сложность:
Условие: Дано бинарное дерево. Представьте, что вы стоите справа от дерева. Верните значения узлов, видимые справа налево (сверху вниз).
Примеры:
Ввод: root = [1,2,3,null,5,null,4]
Вывод: [1,3,4]
Ввод: root = [1,null,3]
Вывод: [1,3]
Ввод: root = []
Вывод: []
Ограничения:
💡 Подсказка: Используйте BFS с обработкой по уровням. Добавляйте в результат последний узел каждого уровня.
Решение:
from collections import deque
def rightSideView(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
for i in range(len(queue)):
node = queue.popleft()
if i == len(queue) - 1: # Последний узел уровня
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return resultОбъяснение:
Сложность:
Условие: Дано бинарное дерево. Найдите его минимальную глубину.
Минимальная глубина — это количество узлов вдоль кратчайшего пути от корневого узла до ближайшего листового узла.
Примеры:
Ввод: root = [3,9,20,null,null,15,7]
Вывод: 2
Ввод: root = [2,null,3,null,4,null,5,null,6]
Вывод: 5
Ограничения:
💡 Подсказка: Используйте BFS. Первый найденный лист даёт минимальную глубину.
Решение:
from collections import deque
def minDepth(root):
if not root:
return 0
queue = deque([(root, 1)])
while queue:
node, depth = queue.popleft()
# Первый найденный лист — минимальная глубина
if not node.left and not node.right:
return depth
if node.left:
queue.append((node.left, depth + 1))
if node.right:
queue.append((node.right, depth + 1))
return 0Объяснение:
Сложность:
Проблема: При подсчёте шагов или обработке уровней важно обрабатывать весь уровень за раз.
# ❌ Неправильно — обрабатываем по одному элементу
steps = 0
while queue:
node = queue.popleft()
if is_target(node):
return steps
for neighbor in neighbors(node):
queue.append(neighbor)
steps += 1 # Ошибка: увеличиваем на каждый элемент!
# ✅ Правильно — обрабатываем весь уровень
steps = 0
while queue:
for _ in range(len(queue)): # Фиксируем размер уровня
node = queue.popleft()
if is_target(node):
return steps
for neighbor in neighbors(node):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
steps += 1 # Увеличиваем после обработки всего уровняПочему это неправильно: steps должен увеличиваться после обработки всех узлов текущего уровня, а не после каждого узла.
Проблема: В графах с циклами BFS зациклится без проверки visited.
# ❌ Неправильно — нет проверки visited
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in neighbors(node):
queue.append(neighbor) # Может зациклиться!
# ✅ Правильно — помечаем посещённые
queue = deque([start])
visited = {start}
while queue:
node = queue.popleft()
for neighbor in neighbors(node):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)Почему это неправильно: В графе с циклами или обратными рёбрами BFS будет бесконечно обходить одни и те же узлы.
Проблема: Начальный узел должен быть помечен как посещённый сразу.
# ❌ Неправильно — start не помечен
queue = deque([start])
visited = set() # Пустой!
while queue:
node = queue.popleft()
visited.add(node) # Добавляем при извлечении
# start может быть добавлен повторно через соседей!
# ✅ Правильно — start помечен сразу
queue = deque([start])
visited = {start} # Сразу добавляем startПочему это неправильно: Начальный узел может быть добавлен повторно через соседей.
| Задача | Ключевая идея |
|---|---|
| Level Order | for _ in range(len(queue)) |
| Right Side View | Последний узел уровня (i == len(queue) - 1) |
| Min Depth | Первый лист = минимальная глубина |
BFS: Основы — базовый паттерн для уровневого обхода.
Ключевые приёмы:
for _ in range(len(queue)) — обработка уровняДалее: BFS: Деревья