DFS: Основы

Поиск в глубину — фундаментальный алгоритм обхода графов и деревьев. Идёт «вглубь» до упора, затем возвращается (backtrack).

#1. Суть паттерна

DFS обходит граф/дерево, исследуя каждую ветвь до конца перед переходом к следующей.

#1.1 Термины

Рекурсия — вызов функцией самой себя.

Базовый случай — условие завершения рекурсии.

Стек вызовов — структура данных, хранящая активные вызовы функций.

DFS (Depth-First Search) — поиск в глубину: идём «вглубь» до упора, затем возвращаемся (backtrack).

#Когда применять

✅ Обход дерева — preorder, inorder, postorder
✅ Поиск пути — существует ли путь между узлами
✅ Компоненты связности — подсчёт островов, областей
✅ Топологическая сортировка — порядок зависимостей

#Рекурсивный шаблон

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)

#2. Разбор задач

#Задача 1: Maximum Depth of Binary Tree (LeetCode 104) 🟩 Easy

Ссылка: https://leetcode.com/problems/maximum-depth-of-binary-tree/

Условие: Дано бинарное дерево. Найдите его максимальную глубину.

Примеры:

Ввод: 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)

Объяснение:

Базовый случай: пустое дерево имеет глубину 0
Рекурсивно находим глубину левого и правого поддерева
Глубина дерева = 1 + max(левое, правое)

Сложность:

Время: O(n)
Память: O(h) — высота дерева в стеке рекурсии

#Задача 2: Path Sum (LeetCode 112) 🟩 Easy

Ссылка: https://leetcode.com/problems/path-sum/

Условие: Дано бинарное дерево и целое число 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))

Объяснение:

Базовый случай: пустое дерево — False
Лист: проверяем, равна ли сумма target
Рекурсивно: вычитаем текущее значение из target

Сложность:

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

#Задача 3: Same Tree (LeetCode 100) 🟩 Easy

Ссылка: https://leetcode.com/problems/same-tree/

Условие: Даны два бинарных дерева 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))

Объяснение:

Базовые случаи: оба пустые → True, один пустой → False
Проверяем значения узлов
Рекурсивно проверяем левое и правое поддеревья

Сложность:

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

#Задача 4: Invert Binary Tree (LeetCode 226) 🟩 Easy

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

Условие: Инвертируйте бинарное дерево (поменяйте местами левое и правое поддеревья каждого узла).

Примеры:

Ввод: 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

Объяснение:

Базовый случай: пустое дерево
Меняем местами левое и правое поддеревья
Рекурсивно инвертируем поддеревья

Сложность:

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

#3. ⚠️ Common Mistakes

#❌ Ошибка 1: Забыли базовый случай

# ❌ Неправильно — нет проверки на 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)
    ...

#❌ Ошибка 2: Забыли помечать посещённые

# ❌ Неправильно — нет проверки 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)

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

Задача	Ключевая идея
Max Depth	1 + max(left, right)
Path Sum	Вычитаем из target, проверяем лист
Same Tree	Сравниваем значения и поддеревья
Invert Tree	Меняем left и right местами

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

DFS: Основы — базовый паттерн для обхода деревьев.

Ключевые принципы:

Всегда добавляйте базовый случай (None или visited)
Для деревьев: рекурсивный DFS проще итеративного
Для графов: обязательно помечайте посещённые узлы

Задача

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

Max Depth

1 + max(left, right)

Path Sum

Вычитаем из target, проверяем лист

Same Tree

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

Invert Tree

Меняем left и right местами