Базовое определение дерева

class TreeNode:
    """Узел бинарного дерева"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val      # Значение узла
        self.left = left    # Левый потомок
        self.right = right  # Правый потомок

---

Задача 1: Обход дерева в глубину (DFS)

Описание задачи

Написать функцию для рекурсивного обхода бинарного дерева в глубину (Depth-First Search). DFS — один из фундаментальных алгоритмов обхода графов и деревьев, где мы идём "вглубь" до конца ветки перед тем как возвращаться.

Принципы решения

• Рекурсивный подход: естественно ложится на структуру дерева
• Базовый случай: достижение пустого узла (None)
• Рекурсивный случай: обработка текущего узла и рекурсивные вызовы для потомков
• Три варианта обхода:
  • Pre-order (прямой): узел → левое поддерево → правое поддерево
  • In-order (симметричный): левое поддерево → узел → правое поддерево
  • Post-order (обратный): левое поддерево → правое поддерево → узел

Область применения

• Поиск элементов в дереве
• Копирование деревьев
• Вычисление выражений (синтаксические деревья)
• Создание префиксных/постфиксных записей выражений
• Анализ иерархических структур

Реализация (Pre-order обход)

def dfs_preorder(root):
    """Рекурсивный обход дерева в глубину (pre-order)"""
    if not root:  # Базовый случай: если узел пустой
        return
    
    print(root.val)        # Посещаем текущий узел (pre-order)
    dfs_preorder(root.left)         # Рекурсивно обходим левое поддерево
    dfs_preorder(root.right)        # Рекурсивно обходим правое поддерево

def dfs_inorder(root):
    """Рекурсивный обход дерева в глубину (in-order)"""
    if not root:
        return
    
    dfs_inorder(root.left)          # Сначала левое поддерево
    print(root.val)                 # Затем узел (in-order)
    dfs_inorder(root.right)         # Затем правое поддерево

def dfs_postorder(root):
    """Рекурсивный обход дерева в глубину (post-order)"""
    if not root:
        return
    
    dfs_postorder(root.left)        # Сначала левое поддерево
    dfs_postorder(root.right)       # Затем правое поддерево
    print(root.val)                 # В конце узел (post-order)

---

Задача 2: Обход дерева в ширину (BFS/Level Order)

Описание задачи

Написать функцию для обхода бинарного дерева в ширину (Breadth-First Search). BFS проходит дерево уровень за уровнем, начиная с корня.

Принципы решения

• Использование очереди: FIFO (First-In-First-Out) структура
• Итеративный подход: более естественный для BFS
• Алгоритм:
  1. Добавить корень в очередь
  2. Пока очередь не пуста:
     • Извлечь узел из начала очереди
     • Обработать узел
     • Добавить его потомков в конец очереди

Область применения

• Поиск кратчайшего пути в невзвешенных графах
• Нахождение минимальной глубины дерева
• Поиск соседей на заданном расстоянии
• Обход социальных графов (друзья друзей)
• Поиск в лабиринтах

Реализация

from collections import deque

def bfs(root):
    """Обход дерева в ширину с использованием очереди"""
    if not root:  # Проверка на пустое дерево
        return []
    
    result = []           # Список для хранения результата
    queue = deque([root]) # Очередь, начинаем с корня
    
    while queue:          # Пока очередь не пуста
        node = queue.popleft()      # Берем первый элемент (FIFO)
        result.append(node.val)     # Добавляем его значение
        
        if node.left:               # Если есть левый потомок
            queue.append(node.left) # Добавляем в конец очереди
        if node.right:              # Если есть правый потомок
            queue.append(node.right)
    
    return result

---

Задача 3: Поиск максимальной глубины дерева

Описание задачи

Найти максимальную глубину (высоту) бинарного дерева. Глубина — количество узлов на самом длинном пути от корня до листа.

Принципы решения

• Рекурсивный подход: глубина = 1 + максимум из глубин поддеревьев
• Базовый случай: пустой узел имеет глубину 0
• Post-order обход: сначала вычисляем глубины поддеревьев, потом текущего узла
• Альтернативный BFS подход: подсчет уровней при обходе в ширину

Область применения

• Балансировка деревьев
• Анализ сложности алгоритмов на деревьях
• Оптимизация хранения данных
• Визуализация деревьев
• Определение сбалансированности дерева

Реализация

def max_depth(root):
    """Нахождение максимальной глубины дерева (рекурсивно)"""
    if not root:  # Базовый случай: пустое дерево имеет глубину 0
        return 0
    
    # Рекурсивно находим глубину левого и правого поддеревьев
    left_depth = max_depth(root.left)   # Глубина левого поддерева
    right_depth = max_depth(root.right) # Глубина правого поддерева
    
    # Глубина текущего узла = 1 + максимальная из глубин потомков
    return 1 + max(left_depth, right_depth)

def max_depth_bfs(root):
    """Нахождение максимальной глубины дерева (итеративно, BFS)"""
    if not root:
        return 0
    
    depth = 0
    queue = deque([root])
    
    while queue:
        # Обрабатываем все узлы текущего уровня
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        depth += 1  # Увеличиваем счетчик уровня после обработки всех узлов уровня
    
    return depth

---

Задача 4: Проверка симметричности дерева

Описание задачи

Проверить, является ли бинарное дерево симметричным относительно своего центра (зеркальным).

Принципы решения

• Двойной обход: одновременный обход левой и правой частей
• Рекурсивное сравнение:
  • Левый потомок левого поддерева сравнивается с правым потомком правого поддерева
  • Правый потомок левого поддерева сравнивается с левым потомком правого поддерева
• Итеративный подход: использование двух стеков или очередей

Область применения

• Проверка палиндромных структур
• Анализ симметрии в биологии (билатеральная симметрия)
• Оптимизация хранения симметричных данных
• Компьютерная графика и 3D-моделирование
• Сжатие данных с использованием симметрии

Реализация

def is_symmetric(root):
    """Проверка, является ли дерево симметричным (рекурсивно)"""
    def is_mirror(left, right):
        """Вспомогательная функция для проверки зеркальности двух поддеревьев"""
        # Базовые случаи
        if not left and not right:  # Оба узла пустые - симметрично
            return True
        if not left or not right:   # Только один узел пустой - несимметрично
            return False
        if left.val != right.val:   # Значения узлов не совпадают
            return False
        
        # Рекурсивно проверяем зеркальность:
        # левое поддерево левого узла с правым поддеревом правого узла
        # и правое поддерево левого узла с левым поддеревом правого узла
        return (is_mirror(left.left, right.right) and 
                is_mirror(left.right, right.left))
    
    if not root:  # Пустое дерево считается симметричным
        return True
    
    # Запускаем проверку с левого и правого потомков корня
    return is_mirror(root.left, root.right)

def is_symmetric_iterative(root):
    """Проверка симметричности (итеративно с использованием очереди)"""
    if not root:
        return True
    
    queue = deque([(root.left, root.right)])
    
    while queue:
        left, right = queue.popleft()
        
        if not left and not right:
            continue
        if not left or not right:
            return False
        if left.val != right.val:
            return False
        
        # Добавляем пары для сравнения в правильном порядке
        queue.append((left.left, right.right))
        queue.append((left.right, right.left))
    
    return True

---

Задача 5: Поиск пути к узлу

Описание задачи

Найти путь от корня дерева до заданного узла с определенным значением.

Принципы решения

• DFS с backtracking: поиск в глубину с сохранением пути
• Стек для хранения пути: при неудачном поиске удаляем последний узел
• Два этапа:
  1. Поиск целевого узла с сохранением пути
  2. Возврат найденного пути
• Альтернативный подход: поиск с последующим восстановлением пути от родительских ссылок

Область применения

• Навигация по файловым системам
• Поиск в иерархических меню
• Определение цепочки наследования в ООП
• Анализ зависимостей в проектах
• Отладка и трассировка вызовов

Реализация

def find_path(root, target):
    """Нахождение пути от корня к целевому узлу"""
    def dfs(node, path):
        """Рекурсивный поиск с сохранением пути"""
        if not node:  # Узел не существует
            return False
        
        path.append(node.val)  # Добавляем текущий узел в путь
        
        if node.val == target:  # Нашли целевой узел
            return True
        
        # Ищем целевой узел в левом или правом поддереве
        if dfs(node.left, path) or dfs(node.right, path):
            return True  # Узел найден в одном из поддеревьев
        
        # Если узел не найден в поддеревьях, удаляем текущий узел из пути
        path.pop()  # Backtracking - откат
        return False
    
    path = []
    dfs(root, path)
    return path

def find_path_iterative(root, target):
    """Итеративный поиск пути с использованием стека"""
    if not root:
        return []
    
    stack = [(root, [root.val])]  # Стек содержит пары (узел, путь_до_него)
    
    while stack:
        node, path = stack.pop()
        
        if node.val == target:
            return path
        
        if node.right:
            stack.append((node.right, path + [node.right.val]))
        if node.left:
            stack.append((node.left, path + [node.left.val]))
    
    return []

---

Задача 6: Нахождение наименьшего общего предка (LCA)

Описание задачи

Найти наименьшего общего предка (LCA) двух узлов в бинарном дереве. LCA — самый глубокий узел, который является предком обоих заданных узлов.

Принципы решения

• Рекурсивный поиск: обход дерева с поиском обоих узлов
• Три случая:
  1. Текущий узел равен одному из искомых → текущий узел и есть LCA
  2. Узлы найдены в разных поддеревьях → текущий узел LCA
  3. Оба узла в одном поддереве → продолжаем поиск в этом поддереве
• Оптимизация для BST: использование свойств бинарного дерева поиска

Область применения

• Системы контроля версий (Git merge base)
• Биоинформатика (филогенетические деревья)
• Базы данных (иерархические запросы)
• Определение родства в генеалогических деревьях
• Оптимизация запросов в XML/JSON

Реализация

def lowest_common_ancestor(root, p, q):
    """Нахождение наименьшего общего предка двух узлов в бинарном дереве"""
    # Базовые случаи
    if not root or root.val == p or root.val == q:
        # Если нашли один из узлов или дошли до конца
        return root
    
    # Рекурсивно ищем узлы в левом и правом поддеревьях
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    
    if left and right:  # Узлы найдены в разных поддеревьях
        return root     # Текущий узел - их общий предок
    
    # Возвращаем ненулевой результат (если оба None, вернется None)
    return left if left else right

def lca_bst(root, p, q):
    """LCA для бинарного дерева поиска (оптимизированная версия)"""
    # В BST можем использовать значения узлов для навигации
    while root:
        if p < root.val and q < root.val:
            # Оба узла в левом поддереве
            root = root.left
        elif p > root.val and q > root.val:
            # Оба узла в правом поддереве
            root = root.right
        else:
            # Узлы в разных поддеревьях или один из них равен текущему
            return root
    return None

---

Задача 7: Проверка бинарного дерева поиска (BST)

Описание задачи

Проверить, является ли бинарное дерево бинарным деревом поиска (BST). В BST для каждого узла:

• Все узлы левого поддерева имеют значения меньше значения узла
• Все узлы правого поддерева имеют значения больше значения узла

Принципы решения

• Валидация с границами: передаем минимальное и максимальное допустимые значения
• In-order обход: в BST in-order обход дает отсортированную последовательность
• Рекурсивная проверка:
  • Левые потомки должны быть меньше текущего узла
  • Правые потомки должны быть больше текущего узла
• Две стратегии:
  1. Рекурсивная с границами
  2. In-order обход с проверкой сортированности

Область применения

• Проверка корректности структур данных
• Оптимизация поисковых операций
• Базы данных (индексы B-деревья)
• Сортировка и поиск данных
• Реализация множеств и словарей

Реализация

def is_valid_bst(root):
    """Проверка, является ли дерево BST (рекурсивно с границами)"""
    def validate(node, min_val, max_val):
        """Вспомогательная функция с границами допустимых значений"""
        if not node:  # Пустой узел - валидный BST
            return True
        
        # Проверяем, что значение узла в пределах границ
        # Для корня границы: (-∞, +∞)
        # Для левого потомка: (-∞, значение_родителя)
        # Для правого потомка: (значение_родителя, +∞)
        if node.val <= min_val or node.val >= max_val:
            return False
        
        # Рекурсивно проверяем левое и правое поддеревья
        # Для левого поддерева максимум - текущее значение
        # Для правого поддерева минимум - текущее значение
        return (validate(node.left, min_val, node.val) and 
                validate(node.right, node.val, max_val))
    
    # Начинаем с бесконечных границ
    return validate(root, float('-inf'), float('inf'))

def is_valid_bst_inorder(root):
    """Проверка BST с использованием in-order обхода"""
    def inorder(node):
        """In-order обход с проверкой сортированности"""
        if not node:
            return True
        
        # Сначала проверяем левое поддерево
        if not inorder(node.left):
            return False
        
        # Проверяем, что текущее значение больше предыдущего
        if node.val <= self.prev:
            return False
        self.prev = node.val
        
        # Затем проверяем правое поддерево
        return inorder(node.right)
    
    self.prev = float('-inf')
    return inorder(root)

---

Задача 8: Преобразование отсортированного массива в BST

Описание задачи

Преобразовать отсортированный по возрастанию массив в сбалансированное бинарное дерево поиска.

Принципы решения

• Разделяй и властвуй: рекурсивное разделение массива пополам
• Середина массива как корень: обеспечивает сбалансированность
• Рекурсивное построение:
  • Корень = серединный элемент
  • Левое поддерево = левая половина массива
  • Правое поддерево = правая половина массива
• Балансировка: автоматическая при выборе середины

Область применения

• Создание сбалансированных структур данных из отсортированных данных
• Оптимизация поисковых операций
• Преобразование списков в деревья для быстрого поиска
• Построение индексов баз данных
• Реализация интервальных деревьев

Реализация

def sorted_array_to_bst(nums):
    """Создание сбалансированного BST из отсортированного массива"""
    def helper(left, right):
        """Рекурсивная функция построения дерева из подмассива"""
        if left > right:  # Базовый случай: пустой подмассив
            return None
        
        mid = (left + right) // 2  # Индекс середины текущего отрезка
        
        # Корень - серединный элемент (обеспечивает сбалансированность)
        root = TreeNode(nums[mid])
        
        # Рекурсивно строим левое и правое поддеревья
        # Левое поддерево из левой половины массива (элементы < корня)
        root.left = helper(left, mid - 1)
        
        # Правое поддерево из правой половины массива (элементы > корня)
        root.right = helper(mid + 1, right)
        
        return root
    
    return helper(0, len(nums) - 1)  # Начинаем со всего массива

# Пример использования:
# Вход: [-10, -3, 0, 5, 9]
# Результат: сбалансированное BST
#       0
#      / \
#    -3   9
#    /   /
# -10   5

---

Задача 9: Итеративный обход дерева

Описание задачи

Реализовать итеративный (нерекурсивный) обход бинарного дерева с использованием стека.

Принципы решения

• Использование стека: LIFO (Last-In-First-Out) структура
• Имитация рекурсии: стек заменяет call stack рекурсии
• Три варианта для разных порядков обхода:
  • Pre-order: узел → стек правого потомка → стек левого потомка
  • In-order: движение влево до конца, затем обработка, затем вправо
  • Post-order: два стека или модифицированный pre-order с обращением
• Алгоритм для in-order:
  1. Идем влево до конца, добавляя узлы в стек
  2. Извлекаем узел из стека, обрабатываем его
  3. Переходим к правому поддереву

Область применения

• Избежание переполнения стека вызовов для глубоких деревьев
• Контроль над процессом обхода
• Возможность приостановки и возобновления обхода
• Реализация итераторов для деревьев
• Обход в ограниченной памяти

Реализация

def inorder_traversal_iterative(root):
    """Итеративный inorder обход дерева"""
    result = []      # Результирующий список значений
    stack = []       # Стек для хранения узлов
    current = root   # Текущий узел
    
    while current or stack:  # Пока есть узлы для обработки
        # Добираемся до самого левого узла
        while current:
            stack.append(current)     # Добавляем узел в стек
            current = current.left    # Переходим к левому потомку
        
        # Извлекаем узел из стека (самый левый из необработанных)
        current = stack.pop()
        result.append(current.val)    # Обрабатываем узел
        
        # Переходим к правому поддереву
        current = current.right
    
    return result

def preorder_traversal_iterative(root):
    """Итеративный preorder обход дерева"""
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        
        # Сначала добавляем правый потомок, потом левый
        # (чтобы левый обрабатывался первым)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

def postorder_traversal_iterative(root):
    """Итеративный postorder обход дерева (используя два стека)"""
    if not root:
        return []
    
    result = []
    stack1 = [root]
    stack2 = []
    
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    
    while stack2:
        result.append(stack2.pop().val)
    
    return result

---

Задача 10: Сериализация и десериализация дерева

Описание задачи

Преобразовать бинарное дерево в строку (сериализация) и восстановить дерево из строки (десериализация).

Принципы решения

• Выбор формата представления:
  • Pre-order обход с маркерами для пустых узлов
  • JSON/XML форматы
  • Двоичное представление
• Сериализация:
  • Рекурсивный обход с записью значений и маркеров null
  • Разделители для различения узлов
• Десериализация:
  • Разбор строки на токены
  • Рекурсивное восстановление в том же порядке, что и обход
  • Использование итератора или индекса для чтения токенов

Область применения

• Сохранение деревьев в файлы
• Передача деревьев по сети
• Кэширование структур данных
• Создание контрольных точек (checkpointing)
• Сериализация AST (Abstract Syntax Trees) в компиляторах

Реализация

class Codec:
    """Класс для сериализации и десериализации бинарного дерева"""
    
    def serialize(self, root):
        """Преобразование дерева в строку (pre-order с маркерами None)"""
        def dfs(node):
            """Рекурсивная сериализация с pre-order обходом"""
            if not node:  # Для пустого узла используем специальный маркер
                return "None,"
            
            # Формат: значение,левое_поддерево,правое_поддерево
            return str(node.val) + "," + dfs(node.left) + dfs(node.right)
        
        return dfs(root)
    
    def deserialize(self, data):
        """Восстановление дерева из строки"""
        def dfs(nodes):
            """Рекурсивное восстановление дерева из списка токенов"""
            val = next(nodes)  # Берем следующее значение из итератора
            
            if val == "None":  # Маркер пустого узла
                return None
            
            # Создаем узел с текущим значением
            node = TreeNode(int(val))
            
            # Рекурсивно восстанавливаем левое и правое поддеревья
            # Порядок соответствует pre-order обходу при сериализации
            node.left = dfs(nodes)   # Восстанавливаем левое поддерево
            node.right = dfs(nodes)  # Восстанавливаем правое поддерево
            
            return node
        
        # Создаем итератор из списка значений, разделенных запятыми
        nodes_iter = iter(data.split(","))
        return dfs(nodes_iter)

    def serialize_bfs(self, root):
        """Сериализация с использованием BFS (уровень за уровнем)"""
        if not root:
            return ""
        
        result = []
        queue = deque([root])
        
        while queue:
            node = queue.popleft()
            
            if node:
                result.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append("None")
        
        return ",".join(result)

Советы для решения задач на деревья

1. Выбор стратегии обхода:

   • DFS (рекурсия/стек) для работы с путями и глубиной
   • BFS (очередь) для работы с уровнями и шириной

2. Шаблоны решения:

   • Рекурсия с базовым случаем для None
   • Вспомогательные функции для сложных задач
   • Использование структур данных (стек, очередь, словарь)

3. Оптимизации:

   • Мемоизация для повторяющихся вычислений
   • Ранний выход при нахождении решения
   • Использование свойств конкретных типов деревьев (BST)

4. Тестирование:

   • Пустое дерево
   • Дерево из одного узла
   • Вырожденное дерево (связанный список)
   • Полное сбалансированное дерево
   • Дерево с отрицательными значениями

Это полное пособие покрывает основные задачи на деревья в Python с детальными объяснениями принципов решения и областей применения каждого алгоритма.