Mediumbfstree
Решить задачу Binary Tree Level Order Traversal (LeetCode 102)?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
LeetCode 102. Обход binary tree по уровням, вернуть list of lists. BFS с queue. O(n) время, O(n) память.
from collections import deque
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue) # фиксируем размер уровня
level = []
for _ in range(level_size):
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Ключ: level_size = len(queue) перед внутренним циклом, чтобы process ровно один уровень. Связанные: reverse level order (107), zigzag (103), right side view (199), populate next right pointer (116). Альтернатива — DFS с уровнем.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.