Distance K, Average of Levels, Cousins.
Обход деревьев с помощью BFS. Поиск узлов на заданном расстоянии, конвертация дерева в граф.
Условие:
Дано бинарное дерево с корневым узлом 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
Вывод: []
Ограничения:
💡 Подсказка: Преобразуйте дерево в неориентированный граф (добавьте рёбра к родителям). Затем используйте 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Объяснение:
Сложность:
Условие: Дано бинарное дерево. Верните среднее значение значений узлов на каждом уровне в виде массива.
Примеры:
Ввод: 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]
Ограничения:
💡 Подсказка: Стандартный 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Объяснение:
Сложность:
Условие: Дано бинарное дерево. Верните массив максимальных значений из каждого уровня дерева.
Примеры:
Ввод: root = [1,3,2,5,3,null,9]
Вывод: [1,3,9]
Ввод: root = [1,2,3]
Вывод: [1,3]
Ограничения:
💡 Подсказка: 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Объяснение:
Сложность:
Условие: В бинарном дереве два узла называются кузенами, если они находятся на одной глубине, но имеют разных родителей.
Даны два узла 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
Ограничения:
💡 Подсказка: 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])Объяснение:
Сложность:
| Задача | Ключевая идея |
|---|---|
| Distance K | Граф из дерева + BFS от target |
| Average of Levels | Сумма / count на уровне |
| Largest Value | max() на каждом уровне |
| Cousins | Отслеживать parent и depth |
Проблема: В задаче 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 нужно двигаться и вверх.
Проблема: Проверяем только глубину, забывая про родителей.
# ❌ Неправильно — только глубина
return x_depth == y_depth
# ✅ Правильно — глубина И родители
return x_depth == y_depth and x_parent != y_parentПочему это неправильно: Кузены должны быть на одной глубине, но с разными родителями.
BFS: Задачи на деревья — обход деревьев с поиском на расстоянии и агрегацией по уровням.
Ключевые приёмы:
Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.