0Pricing
DSA Interview Prep · Урок

Класс TreeNode и обход BFS по уровням

Создавайте двоичные деревья из массивов, реализуйте BFS с deque для вывода по уровням и решайте задачу поиска максимальной глубины с помощью BFS

«Класс TreeNode и обход BFS по уровням» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.

Основы класса TreeNode

Двоичное дерево — это иерархическая структура данных, в которой у каждого узла не более двух потомков, называемых левым и правым. В Python узел моделируется с помощью простого класса: class TreeNode: def __init__(self, val=0, left=None, right=None). Каждая задача о деревьях на собеседовании начинается с этого определения — Вы увидите его почти в каждой заготовке задачи о деревьях на LeetCode.

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

# Build a small tree manually:
#       1
#      / \
#     2   3
#    / \
#   4   5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(root.val, root.left.val, root.right.val)

Построение деревьев из массивов

В задачах на собеседованиях дерево часто представлено в виде массива в порядке уровней, где None обозначает отсутствующие узлы. Для заданного индекса i левый потомок находится по индексу 2i+1, а правый — по индексу 2i+2. Вспомогательная функция, десериализующая этот массив в связанные TreeNodes, — полезный инструмент, который экономит время во время практических занятий.

from collections import deque

def build_tree(arr):
    if not arr or arr[0] is None:
        return None
    root = TreeNode(arr[0])
    q = deque([root])
    i = 1
    while q and i < len(arr):
        node = q.popleft()
        if i < len(arr) and arr[i] is not None:
            node.left = TreeNode(arr[i])
            q.append(node.left)
        i += 1
        if i < len(arr) and arr[i] is not None:
            node.right = TreeNode(arr[i])
            q.append(node.right)
        i += 1
    return root

root = build_tree([1, 2, 3, 4, 5, None, 6])
print(root.val, root.left.val, root.right.val)

Что такое BFS и зачем нужна очередь

Поиск в ширину (BFS) посещает все узлы на глубине d, прежде чем посетить какой-либо узел на глубине d+1. Именно это обхождение по уровням обеспечивает очередь (FIFO): мы помещаем корень в очередь, затем обрабатываем узлы по одному и по ходу добавляем в очередь потомков каждого узла. collections.deque в Python предоставляет операции O(1) appendleft и popleft, поэтому для этой задачи он подходит лучше обычного списка.

from collections import deque

def bfs_print(root):
    if not root:
        return
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.val, end=' ')
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
bfs_print(root)  # 1 2 3 4

BFS в порядке уровней: группировка по уровням

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

from collections import deque

def level_order(root):
    if not root:
        return []
    result = []
    q = deque([root])
    while q:
        level_size = len(q)
        level = []
        for _ in range(level_size):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(level)
    return result

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(level_order(root))  # [[1], [2, 3], [4]]

Максимальная глубина с помощью BFS

Максимальная глубина бинарного дерева равна количеству уровней в его обходе BFS. Просто подсчитайте, сколько раз Вы завершили цикл обработки уровня. Это даёт решение со временем O(n) и памятью O(w), где w — максимальная ширина дерева. Для сбалансированного дерева w равно O(n/2), поэтому в худшем случае требуется O(n) памяти.

from collections import deque

def max_depth_bfs(root):
    if not root:
        return 0
    depth = 0
    q = deque([root])
    while q:
        depth += 1
        for _ in range(len(q)):
            node = q.popleft()
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
    return depth

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(max_depth_bfs(root))  # 3

Вид справа на бинарное дерево

Вид справа возвращает последний видимый узел, если смотреть на дерево справа, то есть последний элемент каждого уровня при обходе BFS. Это непосредственное применение BFS в порядке уровней: добавляйте последний узел на каждом уровне. Временная сложность равна O(n), а пространственная — O(w) для очереди.

from collections import deque

def right_side_view(root):
    if not root:
        return []
    result = []
    q = deque([root])
    while q:
        level_size = len(q)
        for i in range(level_size):
            node = q.popleft()
            if i == level_size - 1:
                result.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
    return result

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
print(right_side_view(root))  # [1, 3, 5]

Зигзагообразный обход по уровням

При зигзагообразном обходе нечётные уровни собираются слева направо, а чётные — справа налево. Самая понятная реализация оставляет очередь BFS без изменений и просто разворачивает списки чередующихся уровней перед добавлением их в результат. Направление отслеживается с помощью логического флага, который меняется на каждом уровне. Это позволяет избежать усложнения внутреннего цикла из-за двусторонней очереди.

from collections import deque

def zigzag_level_order(root):
    if not root:
        return []
    result = []
    q = deque([root])
    left_to_right = True
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(level if left_to_right else level[::-1])
        left_to_right = not left_to_right
    return result

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(zigzag_level_order(root))

Анализ пространственной сложности BFS

BFS использует O(w) памяти, где w — максимальная ширина дерева. Для идеального двоичного дерева с n узлами на последнем уровне находится (n+1)/2 узлов, поэтому в очереди BFS одновременно может находиться до n/2 узлов. Поэтому по объёму памяти BFS хуже, чем DFS (O(h)), для широких сбалансированных деревьев, но лучше для глубоких вырожденных деревьев, где глубина стека вызовов DFS равна n.

# Space comparison: BFS vs DFS on a complete binary tree
# n=15 nodes, height=4
# BFS max queue size = 8 (last level)
# DFS max call stack = 4 (height)

# For a skewed tree (like a linked list):
# n=1000 nodes
# BFS max queue size = 1 (always 1 node per level)
# DFS max call stack = 1000 (recursion depth -> stack overflow!)

from collections import deque

def skewed_tree(n):
    root = TreeNode(1)
    cur = root
    for i in range(2, n+1):
        cur.right = TreeNode(i)
        cur = cur.right
    return root

root = skewed_tree(10)
print('BFS on skewed tree is safe')

Среднее значение на уровнях двоичного дерева

Вычисление среднего значения на каждом уровне — ещё одно непосредственное применение BFS. Сложите все значения на уровне, разделите сумму на количество узлов и добавьте результат в список. Эта задача проверяет, умеете ли Вы выполнять арифметические действия внутри цикла по уровням. В Python 3 всегда используйте float-деление — оператор /, — и в начале обработайте случай пустого дерева.

from collections import deque

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

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(average_of_levels(root))  # [3.0, 14.5, 11.0]

Минимальная глубина с помощью BFS

Минимальная глубина — это расстояние от корня до ближайшего листового узла, то есть узла без потомков. BFS находит её оптимальным образом: первый листовой узел, встреченный при обходе по уровням, гарантированно находится на минимальной глубине. Верните текущую глубину сразу после обнаружения листа. В худшем случае сложность составляет O(n), но для сбалансированных деревьев обход часто завершается значительно раньше.

from collections import deque

def min_depth(root):
    if not root:
        return 0
    q = deque([(root, 1)])
    while q:
        node, depth = q.popleft()
        # A leaf has no children
        if not node.left and not node.right:
            return depth
        if node.left:
            q.append((node.left, depth + 1))
        if node.right:
            q.append((node.right, depth + 1))
    return 0

root = TreeNode(2)
root.left = TreeNode(3)
root.left.left = TreeNode(4)
root.right = TreeNode(5)  # leaf at depth 2
print(min_depth(root))  # 2

Связывание соседних узлов на уровне

В задаче заполнения указателей на соседей справа требуется связать каждый узел с его соседом справа на том же уровне. С BFS это просто: внутри цикла по каждому уровню задайте node.next = q[0] для всех узлов, кроме последнего. Это классический пример, когда BFS делает решение очевидным, тогда как DFS требует тщательного отслеживания указателей между поддеревьями.

from collections import deque

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

def connect(root):
    if not root:
        return root
    q = deque([root])
    while q:
        size = len(q)
        for i in range(size):
            node = q.popleft()
            if i < size - 1:
                node.next = q[0]
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
    return root

print('BFS connect: O(n) time, O(w) space')

Быстрая проверка

Проверьте, насколько хорошо Вы усвоили понятия «структуры данных и алгоритмы — подготовка к техническому собеседованию» из этого урока.

Итоги урока

В этом уроке Вы изучили: определение класса TreeNode и построение деревьев из массивов, обход BFS по уровням с использованием двусторонней очереди и приём с размером уровня для группировки узлов, а также применения, включая максимальную глубину, минимальную глубину, вид дерева справа, зигзагообразный обход и средние значения по уровням. Далее мы рассмотрим рекурсивные порядки обхода DFS.

Часто задаваемые вопросы

Урок «Класс TreeNode и обход BFS по уровням» бесплатный?

Да — полный текст урока «Класс TreeNode и обход BFS по уровням» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Класс TreeNode и обход BFS по уровням»?

Создавайте двоичные деревья из массивов, реализуйте BFS с deque для вывода по уровням и решайте задачу поиска максимальной глубины с помощью BFS Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать DSA Interview Prep?

Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.

Сколько времени занимает урок «Класс TreeNode и обход BFS по уровням»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке DSA Interview Prep?

Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Класс TreeNode и обход BFS по уровням
  2. DFS: симметричный, прямой и обратный обход
  3. Диаметр, высота и сбалансированные деревья
  4. Сумма путей и наименьший общий предок
← Назад к DSA Interview Prep