BFS: Задачи на деревья

Обход деревьев с помощью BFS. Поиск узлов на заданном расстоянии, конвертация дерева в граф.

#1. All Nodes Distance K in Binary Tree (LeetCode 863) 🟦 Medium

Ссылка: https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/

Условие: Дано бинарное дерево с корневым узлом root, целевой узел target и целое число k. Верните массив значений всех узлов, находящихся на расстоянии k от целевого узла.

Примеры:

Ввод: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Вывод: [7,4,1]

Ввод: root = [1], target = 1, k = 3
Вывод: []

Ограничения:

Количество узлов в дереве в диапазоне [1, 500]
0 <= Node.val <= 500
target существует в дереве

💡 Подсказка: Преобразуйте дерево в неориентированный граф (добавьте рёбра к родителям). Затем используйте BFS от target.

Решение:

from collections import deque, defaultdict

def distanceK(root, target, k):
    # Строим граф из дерева
    graph = defaultdict(list)

    def build_graph(node, parent):
        if node and parent:
            graph[node.val].append(parent.val)
            graph[parent.val].append(node.val)
        if node.left:
            build_graph(node.left, node)
        if node.right:
            build_graph(node.right, node)

    build_graph(root, None)

    # BFS от target
    queue = deque([(target.val, 0)])
    visited = {target.val}
    result = []

    while queue:
        node, dist = queue.popleft()

        if dist == k:
            result.append(node)
        elif dist < k:
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, dist + 1))

    return result

Объяснение:

В дереве можно двигаться только вниз
Для поиска на расстоянии k нужно двигаться и вверх к родителю
Строим неориентированный граф, добавляя рёбра node ↔ parent

Сложность:

Время: O(n)
Память: O(n)

#2. Average of Levels in Binary Tree (LeetCode 637) 🟩 Easy

Ссылка: https://leetcode.com/problems/average-of-levels-in-binary-tree/

Условие: Дано бинарное дерево. Верните среднее значение значений узлов на каждом уровне в виде массива.

Примеры:

Ввод: root = [3,9,20,null,null,15,7]
Вывод: [3.00000,14.50000,11.00000]
Объяснение: Уровень 0: 3, уровень 1: (9+20)/2=14.5, уровень 2: (15+7)/2=11

Ввод: root = [3,9,20,15,7]
Вывод: [3.00000,14.50000,11.00000]

Ограничения:

Количество узлов в дереве в диапазоне [1, 10⁴]
-2³¹ <= Node.val <= 2³¹ - 1

💡 Подсказка: Стандартный BFS с обработкой по уровням. Считайте сумму значений на каждом уровне.

Решение:

from collections import deque

def averageOfLevels(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_sum = 0
        level_count = len(queue)

        for _ in range(level_count):
            node = queue.popleft()
            level_sum += node.val

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level_sum / level_count)

    return result

Объяснение:

Обрабатываем каждый уровень целиком
Считаем сумму значений и количество узлов на уровне
Делим сумму на количество для среднего

Сложность:

Время: O(n)
Память: O(w) — ширина дерева

#3. Largest Value in Each Tree Row (LeetCode 515) 🟦 Medium

Ссылка: https://leetcode.com/problems/find-largest-value-in-each-tree-row/

Условие: Дано бинарное дерево. Верните массив максимальных значений из каждого уровня дерева.

Примеры:

Ввод: root = [1,3,2,5,3,null,9]
Вывод: [1,3,9]

Ввод: root = [1,2,3]
Вывод: [1,3]

Ограничения:

Количество узлов в дереве в диапазоне [0, 10⁴]
-2³¹ <= Node.val <= 2³¹ - 1

💡 Подсказка: BFS с обработкой по уровням. Находите максимум на каждом уровне.

Решение:

from collections import deque

def largestValues(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_max = float('-inf')

        for _ in range(len(queue)):
            node = queue.popleft()
            level_max = max(level_max, node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level_max)

    return result

Объяснение:

Обрабатываем каждый уровень целиком
Находим максимум на уровне через max()
Добавляем максимум в результат

Сложность:

Время: O(n)
Память: O(w)

#4. Cousins in Binary Tree (LeetCode 993) 🟩 Easy

Ссылка: https://leetcode.com/problems/cousins-in-binary-tree/

Условие: В бинарном дереве два узла называются кузенами, если они находятся на одной глубине, но имеют разных родителей.

Даны два узла x и y. Верните true, если они кузены, иначе false.

Примеры:

Ввод: root = [1,2,3,4], x = 4, y = 3
Вывод: false
Объяснение: Узел 4 и 3 не на одной глубине

Ввод: root = [1,2,3,null,4,null,5], x = 5, y = 4
Вывод: true

Ограничения:

Количество узлов в дереве в диапазоне [2, 100]
1 <= Node.val <= 100
x и y существуют в дереве

💡 Подсказка: BFS с отслеживанием родителя и глубины для каждого узла.

Решение:

from collections import deque

def isCousins(root, x, y):
    if not root:
        return False

    queue = deque([(root, None, 0)])  # (node, parent, depth)
    x_info = None
    y_info = None

    while queue:
        node, parent, depth = queue.popleft()

        if node.val == x:
            x_info = (parent, depth)
        if node.val == y:
            y_info = (parent, depth)

        if x_info and y_info:
            break

        if node.left:
            queue.append((node.left, node, depth + 1))
        if node.right:
            queue.append((node.right, node, depth + 1))

    # Проверяем: одинаковая глубина, разные родители
    return (x_info[1] == y_info[1] and x_info[0] != y_info[0])

Объяснение:

Храним (узел, родитель, глубина) в очереди
Находим информацию для x и y
Проверяем: одинаковая глубина И разные родители

Сложность:

Время: O(n)
Память: O(w)

#5. Шпаргалка

Задача	Ключевая идея
Distance K	Граф из дерева + BFS от target
Average of Levels	Сумма / count на уровне
Largest Value	max() на каждом уровне
Cousins	Отслеживать parent и depth

#6. ⚠️ Common Mistakes

#❌ Ошибка 1: Забыли добавить рёбра к родителям

Проблема: В задаче Distance K нельзя найти узлы на расстоянии k без движения вверх.

# ❌ Неправильно — только дети
graph[node.val].append(node.left.val)
graph[node.val].append(node.right.val)

# ✅ Правильно — двусторонние рёбра
if node and parent:
    graph[node.val].append(parent.val)
    graph[parent.val].append(node.val)

Почему это неправильно: В дереве можно двигаться только вниз. Для поиска на расстоянии k нужно двигаться и вверх.

#❌ Ошибка 2: Неправильная проверка кузенов

Проблема: Проверяем только глубину, забывая про родителей.

# ❌ Неправильно — только глубина
return x_depth == y_depth

# ✅ Правильно — глубина И родители
return x_depth == y_depth and x_parent != y_parent

Почему это неправильно: Кузены должны быть на одной глубине, но с разными родителями.

#7. Заключение

BFS: Задачи на деревья — обход деревьев с поиском на расстоянии и агрегацией по уровням.

Ключевые приёмы:

Конвертация дерева в граф для движения вверх
Отслеживание (parent, depth) для каждого узла
Агрегация (sum, max, average) на каждом уровне

Ввод: root = [3,9,20,null,null,15,7] Вывод: [3.00000,14.50000,11.00000] Объяснение: Уровень 0: 3, уровень 1: (9+20)/2=14.5, уровень 2: (15+7)/2=11 Ввод: root = [3,9,20,15,7] Вывод: [3.00000,14.50000,11.00000]

Ввод: root = [1,2,3,4], x = 4, y = 3 Вывод: false Объяснение: Узел 4 и 3 не на одной глубине Ввод: root = [1,2,3,null,4,null,5], x = 5, y = 4 Вывод: true

Задача

Ключевая идея

Distance K

Граф из дерева + BFS от target

Average of Levels

Сумма / count на уровне

Largest Value

max() на каждом уровне

Cousins

Отслеживать parent и depth

BFS: Деревья