Maximum Depth, Path Sum, Same Tree, Invert Tree.
Поиск в глубину — фундаментальный алгоритм обхода графов и деревьев. Идёт «вглубь» до упора, затем возвращается (backtrack).
DFS обходит граф/дерево, исследуя каждую ветвь до конца перед переходом к следующей.
Рекурсия — вызов функцией самой себя.
Базовый случай — условие завершения рекурсии.
Стек вызовов — структура данных, хранящая активные вызовы функций.
DFS (Depth-First Search) — поиск в глубину: идём «вглубь» до упора, затем возвращаемся (backtrack).
def dfs_recursive(node, visited):
if node is None or node in visited:
return
visited.add(node)
# Обработка узла (preorder)
process(node)
for neighbor in node.neighbors:
dfs_recursive(neighbor, visited)Условие: Дано бинарное дерево. Найдите его максимальную глубину.
Примеры:
Ввод: root = [3, 9, 20, null, null, 15, 7]
Вывод: 3
Ввод: root = [1, null, 2]
Вывод: 2
Решение:
def maxDepth(root):
if not root:
return 0
left_depth = maxDepth(root.left)
right_depth = maxDepth(root.right)
return 1 + max(left_depth, right_depth)Объяснение:
Сложность:
Условие:
Дано бинарное дерево и целое число targetSum. Определите, существует ли путь от корня к листу, где сумма значений узла равна targetSum.
Примеры:
Ввод: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Вывод: true
Ввод: root = [1,2,3], targetSum = 5
Вывод: false
Решение:
def hasPathSum(root, targetSum):
if not root:
return False
# Лист
if not root.left and not root.right:
return root.val == targetSum
# Рекурсивно проверяем поддеревья
return (hasPathSum(root.left, targetSum - root.val) or
hasPathSum(root.right, targetSum - root.val))Объяснение:
Сложность:
Условие:
Даны два бинарных дерева p и q. Проверьте, одинаковы ли они.
Примеры:
Ввод: p = [1,2,3], q = [1,2,3]
Вывод: true
Ввод: p = [1,2], q = [1,null,2]
Вывод: false
Решение:
def isSameTree(p, q):
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return (isSameTree(p.left, q.left) and
isSameTree(p.right, q.right))Объяснение:
Сложность:
Условие: Инвертируйте бинарное дерево (поменяйте местами левое и правое поддеревья каждого узла).
Примеры:
Ввод: root = [4,2,7,1,3,6,9]
Вывод: [4,7,2,9,6,3,1]
Решение:
def invertTree(root):
if not root:
return None
# Меняем местами левое и правое
root.left, root.right = invertTree(root.right), invertTree(root.left)
return rootОбъяснение:
Сложность:
# ❌ Неправильно — нет проверки на None
def dfs(node, visited):
visited.add(node)
for neighbor in node.neighbors:
dfs(neighbor, visited) # Бесконечная рекурсия!
# ✅ Правильно
def dfs(node, visited):
if node is None or node in visited: # Базовый случай!
return
visited.add(node)
...# ❌ Неправильно — нет проверки visited
def dfs(node):
process(node)
for neighbor in node.neighbors:
dfs(neighbor) # Зациклится на графе с циклом!
# ✅ Правильно
def dfs(node, visited):
visited.add(node)
for neighbor in node.neighbors:
if neighbor not in visited:
dfs(neighbor, visited)| Задача | Ключевая идея |
|---|---|
| Max Depth | 1 + max(left, right) |
| Path Sum | Вычитаем из target, проверяем лист |
| Same Tree | Сравниваем значения и поддеревья |
| Invert Tree | Меняем left и right местами |
DFS: Основы — базовый паттерн для обхода деревьев.
Ключевые принципы:
Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.