Обход бинарного дерева по уровням (BFS): шаблон, зигзаг, вид справа и ширина

Коротко

Обход по уровням (level order traversal) — это поиск в ширину, применённый к дереву. Сам BFS разобран в статье про DFS и BFS, а общий обзор задач на деревья — в отдельном разборе. Здесь сосредоточимся на одном шаблоне и на пяти задачах, которые из него вырастают. На собеседованиях они встречаются постоянно, и отличаются друг от друга двумя-тремя строками.

Дерево для примеров

Все примеры ниже используют один и тот же класс узла и вспомогательную функцию, которая собирает дерево из списка в формате LeetCode. Удобно держать её под рукой, чтобы проверять решения локально.

from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build(values):
    """Строит дерево из списка в формате LeetCode: [3, 9, 20, None, None, 15, 7]."""
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

Заметьте: функция build сама по себе — обход по уровням. Формат LeetCode записывает дерево именно так, слой за слоем, поэтому и восстанавливать его удобнее всего очередью.

Основной пример — дерево [3, 9, 20, None, None, 15, 7]:

        3          уровень 0
       / \
      9   20       уровень 1
         /  \
        15   7     уровень 2

От плоского BFS к уровням

Обычный BFS по дереву выглядит так:

def bfs_flat(root):
    if root is None:
        return []
    order = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        order.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return order


print(bfs_flat(build([3, 9, 20, None, None, 15, 7])))  # [3, 9, 20, 15, 7]

Порядок правильный, но границы уровней потеряны: из [3, 9, 20, 15, 7] не видно, что 9 и 20 стоят рядом, а 15 и 7 — уровнем ниже. В отличие от графа, visited здесь не нужен: в дереве нет циклов, и до каждого узла ведёт ровно один путь.

Почему очередь вообще выдаёт узлы по уровням? Узлы уровня $d$ попадают в очередь раньше любого узла уровня $d+1$, ведь каждый узел уровня $d+1$ — ребёнок какого-то узла уровня $d$ и добавляется только когда родителя достали. Значит, в любой момент очередь содержит хвост одного уровня и начало следующего, и никогда не смешивает три уровня сразу.

Шаблон: очередь и размер уровня

Отсюда главный приём. В момент, когда мы начинаем новый уровень, в очереди лежат ровно узлы этого уровня и больше ничего. Если запомнить их количество, можно достать именно столько узлов, а детей, которые добавятся по ходу, оставить на следующую итерацию.

def level_order(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):  # len вычисляется один раз, до цикла
            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


print(level_order(build([3, 9, 20, None, None, 15, 7])))  # [[3], [9, 20], [15, 7]]

Это решение LeetCode 102 (Binary Tree Level Order Traversal). Его стоит уметь писать не задумываясь: дальше почти каждая задача — этот же код с изменённой обработкой уровня.

Разбор по шагам

Внутри второй итерации очередь успевает побывать в состоянии [20, 15, 7]: узел 20 ещё не обработан, а его дети уже пришли. Если бы цикл шёл «пока очередь не пуста», он бы забрал и 15, и 7 в тот же уровень. Фиксированный range(len(queue)) этого не допускает.

Почему range(len(queue)) безопасен в Python

range(len(queue)) вычисляет длину один раз, при входе в цикл, поэтому добавления в очередь на число итераций не влияют. В Java и C++ так же работает отдельная переменная int size = queue.size() перед циклом. А вот for (int i = 0; i < queue.size(); i++) — уже ошибка: условие перепроверяется на каждом шаге, и размер растёт вместе с добавленными детьми.

Почему deque, а не список

list.pop(0) сдвигает все оставшиеся элементы и стоит $O(k)$. На дереве из миллиона узлов это превращает линейный обход в квадратичный. deque.popleft() работает за $O(1)$ — подробнее об этой структуре в статье про дек.

В JavaScript та же проблема с Array.prototype.shift(). Проще всего обойтись без извлечения из начала: держать текущий уровень массивом и строить следующий рядом.

function levelOrder(root) {
  const result = []
  if (!root) return result
  let level = [root]
  while (level.length > 0) {
    const values = []
    const next = []
    for (const node of level) {
      values.push(node.val)
      if (node.left) next.push(node.left)
      if (node.right) next.push(node.right)
    }
    result.push(values)
    level = next
  }
  return result
}

const node = (val, left = null, right = null) => ({ val, left, right })
const root = node(3, node(9), node(20, node(15), node(7)))
console.log(JSON.stringify(levelOrder(root))) // [[3],[9,20],[15,7]]

Три альтернативы шаблону

Знать их полезно: интервьюер может попросить решить иначе, а иногда другой вариант просто короче.

Два списка вместо очереди. То же, что в JavaScript-версии выше. Границы уровней получаются сами собой, считать размер не нужно.

def level_order_lists(root):
    result = []
    level = [root] if root else []
    while level:
        result.append([node.val for node in level])
        level = [child for node in level for child in (node.left, node.right) if child]
    return result

Глубина вместе с узлом. В очередь кладём пары (узел, глубина). Когда встречаем глубину, для которой ещё нет списка, создаём его. Вариант удобен, если глубина нужна для чего-то ещё, например для подсчёта суммы на конкретном уровне.

def level_order_pairs(root):
    if root is None:
        return []
    result = []
    queue = deque([(root, 0)])
    while queue:
        node, depth = queue.popleft()
        if depth == len(result):
            result.append([])
        result[depth].append(node.val)
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))
    return result

DFS с глубиной. Неожиданно, но обход по уровням можно сделать и рекурсией. Порядок посещения у DFS другой, однако внутри каждого уровня левый узел всё равно добавится раньше правого, потому что левое поддерево обходится первым.

def level_order_dfs(root):
    result = []

    def dfs(node, depth):
        if node is None:
            return
        if depth == len(result):
            result.append([])
        result[depth].append(node.val)
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)

    dfs(root, 0)
    return result

Память здесь $O(h)$ на стек вызовов вместо $O(w)$ на очередь. Для широкого сбалансированного дерева это выгоднее, но на вырожденной «лесенке» из десятков тысяч узлов Python упрётся в лимит рекурсии. Как устроен стек вызовов и почему он переполняется, разобрано в статье про рекурсию.

Зигзаг-обход

LeetCode 103, Binary Tree Zigzag Level Order Traversal. Уровни нужно выдавать попеременно: слева направо, затем справа налево и так далее.

Первая мысль — менять порядок добавления детей в очередь. Это ловушка: если на нечётном уровне класть сначала правого ребёнка, то перевернётся не только следующий уровень, но и порядок внутри поддеревьев, и на третьем уровне всё поедет. Очередь должна работать как обычно, переворачивать нужно только запись значений.

Самый простой способ — собрать уровень и развернуть его через раз: level.reverse(). Это $O(k)$ на уровень, суммарно $O(n)$, то есть асимптотику не портит. Чуть изящнее писать значения в дек с нужного конца:

def zigzag_level_order(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    left_to_right = True
    while queue:
        level = deque()
        for _ in range(len(queue)):
            node = queue.popleft()
            if left_to_right:
                level.append(node.val)
            else:
                level.appendleft(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(list(level))
        left_to_right = not left_to_right
    return result


print(zigzag_level_order(build([1, 2, 3, 4, 5, 6, 7])))
# [[1], [3, 2], [4, 5, 6, 7]]

Есть и третий вариант — два стека, где дети кладутся в разном порядке в зависимости от направления. Он тоже корректен, но в нём легко перепутать порядок, а выигрыша нет. На собеседовании лучше начать с разворота и упомянуть дек как улучшение.

Вид справа (Right Side View)

LeetCode 199, Binary Tree Right Side View. Представьте, что смотрите на дерево справа. Нужно вернуть значения узлов, которые видны, сверху вниз.

Частая ошибка — идти только по правым детям. Контрпример:

      1
     / \
    2   3
   /
  4

Справа видно 1, 3 и 4. Узел 4 растёт слева, но на его уровне правее никого нет. Правильная формулировка: видимый узел — это последний узел каждого уровня.

def right_side_view(root):
    if root is None:
        return []
    view = []
    queue = deque([root])
    while queue:
        size = len(queue)
        for i in range(size):
            node = queue.popleft()
            if i == size - 1:
                view.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return view


print(right_side_view(build([1, 2, 3, 4])))  # [1, 3, 4]
print(right_side_view(build([1, 2, 3, None, 5, None, 4])))  # [1, 3, 4]

Вид слева — то же самое с условием i == 0.

У этой задачи есть красивое DFS-решение. Обходим сначала правое поддерево, потом левое. Первый узел, который мы встретим на новой глубине, и будет самым правым на ней:

def right_side_view_dfs(root):
    view = []

    def dfs(node, depth):
        if node is None:
            return
        if depth == len(view):
            view.append(node.val)
        dfs(node.right, depth + 1)
        dfs(node.left, depth + 1)

    dfs(root, 0)
    return view

Условие depth == len(view) означает «на этой глубине мы ещё никого не видели». Тот же приём работает в DFS-версии обхода по уровням выше.

Средние значения по уровням

LeetCode 637, Average of Levels in Binary Tree. Для каждого уровня вернуть среднее значение узлов. Здесь размер уровня, который мы и так запоминаем, служит знаменателем.

def average_of_levels(root):
    if root is None:
        return []
    averages = []
    queue = deque([root])
    while queue:
        size = len(queue)
        total = 0
        for _ in range(size):
            node = queue.popleft()
            total += node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        averages.append(total / size)
    return averages


print(average_of_levels(build([3, 9, 20, None, None, 15, 7])))  # [3.0, 14.5, 11.0]

В Python целые числа не переполняются, а в Java и C++ это реальный риск: значения узлов в задаче доходят до $2^{31}-1$, и сумма двух таких уже не влезает в int. Сумму держат в long или double. Об этом стоит сказать вслух, даже если пишете на Python, — интервьюеры такое замечают.

По той же схеме решаются «максимум в каждой строке» (LeetCode 515) и «сумма самого глубокого уровня»: меняется только то, что мы накапливаем внутри уровня.

Максимальная ширина дерева

LeetCode 662, Maximum Width of Binary Tree. Самая коварная задача из подборки. Ширина уровня — это расстояние между самым левым и самым правым непустыми узлами, включая пропуски между ними, как если бы дерево было полным.

          1
        /   \
       3     2
      /       \
     5         9
    /         /
   6         7

На последнем уровне всего два узла, но между ними пять пустых позиций полного дерева. Если пронумеровать позиции как в двоичной куче (корень — 0, дети узла $i$ — $2i$ и $2i+1$ относительно начала уровня), то 6 получит позицию 0, а 7 — позицию 6. Ширина: $6 - 0 + 1 = 7$.

Значит, размер уровня здесь бесполезен — нужны позиции. Кладём в очередь пары (узел, индекс), а ширина уровня равна последний индекс − первый индекс + 1.

def width_of_binary_tree(root):
    if root is None:
        return 0
    best = 0
    queue = deque([(root, 0)])
    while queue:
        size = len(queue)
        first = queue[0][1]
        last = queue[-1][1]
        best = max(best, last - first + 1)
        for _ in range(size):
            node, idx = queue.popleft()
            idx -= first  # нормализация: уровень всегда начинается с 0
            if node.left:
                queue.append((node.left, 2 * idx))
            if node.right:
                queue.append((node.right, 2 * idx + 1))
    return best


print(width_of_binary_tree(build([1, 3, 2, 5, 3, None, 9])))  # 4
print(width_of_binary_tree(build([1, 3, 2, 5, None, None, 9, 6, None, 7])))  # 7
print(width_of_binary_tree(build([1, 3, 2, 5])))  # 2

Зачем строка idx -= first? Без неё индексы удваиваются на каждом уровне. Для «лесенки» из 3000 узлов, уходящей вправо, индекс последнего узла был бы $2^{3000}-1$. Python это переживёт, хоть и будет работать с огромными числами. В Java long переполнится уже на глубине 64, а в JavaScript точность Number заканчивается на $2^{53}$, после чего last - first начинает врать.

Нормализация вычитает индекс самого левого узла уровня, поэтому числа остаются в пределах реальной ширины. Разность индексов на уровне от сдвига не меняется, так что ответ тот же.

Почему в нормализованной версии дети нумеруются 2 * idx и 2 * idx + 1, а не 2i + 1 и 2i + 2, как в куче с нуля? Оба варианта корректны: важна только разность между индексами внутри уровня, а она одинакова при любом постоянном сдвиге. Выберите одну схему и не смешивайте.

Минимальная глубина: где BFS выигрывает у DFS

LeetCode 111, Minimum Depth of Binary Tree. Нужно найти расстояние от корня до ближайшего листа. Обход по уровням находит его первым по определению: как только на текущем уровне встретился лист, можно возвращать ответ и не смотреть остальное дерево.

def min_depth(root):
    if root is None:
        return 0
    queue = deque([root])
    depth = 1
    while queue:
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left is None and node.right is None:
                return depth
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        depth += 1
    return depth


print(min_depth(build([3, 9, 20, None, None, 15, 7])))  # 2

DFS-решение обязано обойти всё дерево, чтобы убедиться, что более короткого пути нет. Если у корня один лист рядом и огромное поддерево сбоку, BFS закончит за пару шагов. Это хороший аргумент, когда спрашивают «а почему здесь BFS?».

Обратите внимание на определение листа: узел без обоих детей. Узел с одним ребёнком листом не является, и в DFS-версии на этом спотыкаются чаще всего.

Сложность

Каждый узел попадает в очередь и извлекается из неё ровно один раз, отсюда $O(n)$ по времени. Память определяется максимальным количеством узлов, которые одновременно лежат в очереди, — это ширина самого широкого уровня. У полного бинарного дерева на последнем уровне примерно половина всех узлов, поэтому в худшем случае память $O(n)$. У вырожденной «лесенки» ширина 1, и BFS обходится $O(1)$ дополнительной памяти, зато рекурсивный DFS там тратит $O(n)$ на стек.

Отсюда практическое правило: BFS дешевле по памяти на глубоких узких деревьях, DFS — на широких и сбалансированных, где $h = O(\log n)$.

Типичные ошибки

Уровни слиплись. Внутренний цикл написан как while queue или for i in range(queue.size()) в языке, где условие перепроверяется. Результат — один уровень со всеми узлами.

Список вместо очереди. queue.pop(0) в Python и shift() в JavaScript делают обход квадратичным. На маленьких тестах это незаметно, на больших — Time Limit Exceeded.

Пустое дерево. deque([None]) — непустая очередь, и первая же попытка взять node.val упадёт. Проверка if root is None в начале обязательна.

Зигзаг через порядок детей. Меняется порядок добавления в очередь, и уже на третьем уровне значения идут не в том порядке. Переворачивайте запись, а не обход.

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

Переполнение. Сумма уровня в int для средних и ненормализованные индексы для ширины. В Python обе проблемы скрыты, поэтому их стоит проговорить.

Лишний visited. Не ошибка, но признак того, что шаблон для графа скопирован без понимания. В дереве узел достижим единственным путём, и повторно в очередь не попадёт.

Как это спрашивают на собеседовании

Обход по уровням почти никогда не дают сам по себе: это разминка или первый шаг. Типичная цепочка выглядит так: напишите level order → теперь зигзагом → а что видно справа → можно ли без очереди. Поэтому выгоднее всего выучить один шаблон до автоматизма и знать, какая строка меняется в каждой вариации.

Пара советов по подаче:

• Сначала назовите идею одной фразой: «BFS, и перед каждым уровнем запоминаю размер очереди». Интервьюер сразу понимает, что вы знаете шаблон.
• Сразу проговорите граничные случаи: пустое дерево, один узел, «лесенка».
• Когда спросят про память, не говорите просто $O(n)$. Скажите $O(w)$ и поясните, когда это $O(n)$, а когда $O(1)$. Это ответ уровнем выше.
• Если задача про ширину, начните с вопроса, считаются ли пустые позиции между узлами. Это главная развилка в условии.

Шаблон с очередью и размером уровня занимает десять строк и закрывает добрый десяток задач. Если вы пишете его без подглядывания и можете объяснить, почему очередь не смешивает уровни, большая часть BFS-задач на деревьях на собеседовании уже решена. Следующий шаг — те же идеи на произвольных графах, где появляются visited и кратчайшие пути: с этим поможет 0-1 BFS и алгоритм Дейкстры.