61. Reverse Linked List II

Описание: Развернуть часть связного списка между позициями left и right.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseBetween(head, left, right):
    """
    Разворот части связного списка от left до right
    """
    if not head or left == right:
        return head
    
    dummy = ListNode(0, head)
    prev = dummy
    
    # Находим узел перед left
    for _ in range(left - 1):
        prev = prev.next
    
    # Разворачиваем часть списка
    current = prev.next
    next_node = None
    
    for _ in range(right - left + 1):
        temp = current.next
        current.next = next_node
        next_node = current
        current = temp
    
    # Соединяем развернутую часть
    prev.next.next = current
    prev.next = next_node
    
    return dummy.next

62. Reverse Nodes in k-Group

Описание: Развернуть связный список группами по k узлов.

def reverseKGroup(head, k):
    """
    Разворот связного списка группами по k узлов
    """
    def get_length(node):
        """Вычисляет длину списка"""
        length = 0
        while node:
            length += 1
            node = node.next
        return length
    
    def reverse_group(start, end):
        """Разворачивает группу узлов"""
        prev, curr = None, start
        while curr != end:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        return prev, start
    
    length = get_length(head)
    if length < k or k <= 1:
        return head
    
    dummy = ListNode(0, head)
    prev_group_end = dummy
    
    while length >= k:
        group_start = prev_group_end.next
        group_end = group_start
        
        # Находим конец группы
        for _ in range(k):
            group_end = group_end.next
        
        # Разворачиваем группу
        new_start, new_end = reverse_group(group_start, group_end)
        
        # Соединяем с предыдущей и следующей группами
        prev_group_end.next = new_start
        new_end.next = group_end
        
        prev_group_end = new_end
        length -= k
    
    return dummy.next

63. Remove Nth Node From End of List

Описание: Удалить n-й узел с конца связного списка.

def removeNthFromEnd(head, n):
    """
    Удаление n-го узла с конца связного списка
    """
    dummy = ListNode(0, head)
    first = dummy
    second = dummy
    
    # Первый указатель на n+1 шагов вперед
    for _ in range(n + 1):
        first = first.next
    
    # Двигаем оба указателя до конца
    while first:
        first = first.next
        second = second.next
    
    # Удаляем узел
    second.next = second.next.next
    
    return dummy.next

64. Remove Duplicates from Sorted List II

Описание: Удалить все узлы с дублирующимися значениями из отсортированного списка.

def deleteDuplicates(head):
    """
    Удаление всех узлов с дублирующимися значениями
    """
    dummy = ListNode(0, head)
    prev = dummy
    current = head
    
    while current:
        # Проверяем, есть ли дубликаты текущего значения
        if current.next and current.val == current.next.val:
            # Пропускаем все дубликаты
            while current.next and current.val == current.next.val:
                current = current.next
            prev.next = current.next
        else:
            prev = prev.next
        
        current = current.next
    
    return dummy.next

65. Rotate List

Описание: Циклически сдвинуть связный список вправо на k позиций.

def rotateRight(head, k):
    """
    Циклический сдвиг связного списка вправо на k позиций
    """
    if not head or not head.next or k == 0:
        return head
    
    # Находим длину списка и последний узел
    length = 1
    tail = head
    while tail.next:
        tail = tail.next
        length += 1
    
    # Нормализуем k
    k = k % length
    if k == 0:
        return head
    
    # Находим новый хвост (length - k - 1 шагов от головы)
    new_tail = head
    for _ in range(length - k - 1):
        new_tail = new_tail.next
    
    # Перестраиваем связи
    new_head = new_tail.next
    new_tail.next = None
    tail.next = head
    
    return new_head

66. Partition List

Описание: Разделить связный список так, чтобы все узлы меньше x были перед узлами больше или равными x.

def partition(head, x):
    """
    Разделение связного списка по значению x
    """
    # Создаем два вспомогательных списка
    before_head = ListNode(0)
    after_head = ListNode(0)
    
    before = before_head
    after = after_head
    
    current = head
    
    while current:
        if current.val < x:
            before.next = current
            before = before.next
        else:
            after.next = current
            after = after.next
        
        current = current.next
    
    # Соединяем два списка
    after.next = None
    before.next = after_head.next
    
    return before_head.next

67. LRU Cache

Описание: Реализовать кэш LRU (Least Recently Used).

class ListNode:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        """
        Инициализация LRU кэша
        capacity: максимальная емкость кэша
        """
        self.capacity = capacity
        self.cache = {}  # key -> node
        
        # Инициализируем dummy узлы для двусвязного списка
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _add_node(self, node):
        """
        Добавление узла сразу после head (самый недавно использованный)
        """
        node.prev = self.head
        node.next = self.head.next
        
        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node):
        """
        Удаление узла из списка
        """
        prev_node = node.prev
        next_node = node.next
        
        prev_node.next = next_node
        next_node.prev = prev_node

    def _move_to_head(self, node):
        """
        Перемещение узла в начало (помечаем как недавно использованный)
        """
        self._remove_node(node)
        self._add_node(node)

    def _pop_tail(self):
        """
        Удаление последнего узла (самого старого)
        """
        node = self.tail.prev
        self._remove_node(node)
        return node

    def get(self, key):
        """
        Получение значения по ключу
        """
        if key not in self.cache:
            return -1
        
        node = self.cache[key]
        self._move_to_head(node)
        return node.val

    def put(self, key, value):
        """
        Добавление или обновление значения
        """
        if key in self.cache:
            # Обновляем существующий узел
            node = self.cache[key]
            node.val = value
            self._move_to_head(node)
        else:
            # Создаем новый узел
            node = ListNode(key, value)
            self.cache[key] = node
            self._add_node(node)
            
            # Проверяем емкость
            if len(self.cache) > self.capacity:
                # Удаляем самый старый элемент
                tail = self._pop_tail()
                del self.cache[tail.key]

68. Maximum Depth of Binary Tree

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

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxDepth(root):
    """
    Максимальная глубина бинарного дерева
    Рекурсивное решение
    """
    if not root:
        return 0
    
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    
    return max(left_depth, right_depth) + 1

# Итеративное решение (BFS)
from collections import deque

def maxDepthBFS(root):
    """
    Максимальная глубина бинарного дерева (итеративно, BFS)
    """
    if not root:
        return 0
    
    queue = deque([root])
    depth = 0
    
    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

69. Same Tree

Описание: Проверить, являются ли два бинарных дерева одинаковыми.

def isSameTree(p, q):
    """
    Проверка идентичности двух бинарных деревьев
    """
    # Оба узла None
    if not p and not q:
        return True
    
    # Один из узлов None
    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)

70. Invert Binary Tree

Описание: Инвертировать бинарное дерево (зеркальное отражение).

def invertTree(root):
    """
    Инвертирование бинарного дерева
    """
    if not root:
        return None
    
    # Рекурсивно инвертируем поддеревья
    left = invertTree(root.left)
    right = invertTree(root.right)
    
    # Меняем местами поддеревья
    root.left = right
    root.right = left
    
    return root

# Итеративное решение
def invertTreeIterative(root):
    if not root:
        return None
    
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        
        # Меняем местами левое и правое поддеревья
        node.left, node.right = node.right, node.left
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return root

71. Symmetric Tree

Описание: Проверить, является ли бинарное дерево симметричным.

def isSymmetric(root):
    """
    Проверка симметричности бинарного дерева
    """
    def isMirror(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 isMirror(left.left, right.right) and isMirror(left.right, right.left)
    
    if not root:
        return True
    
    return isMirror(root.left, root.right)

# Итеративное решение
def isSymmetricIterative(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

72. Construct Binary Tree from Preorder and Inorder Traversal

Описание: Построить бинарное дерево по preorder и inorder обходам.

def buildTree(preorder, inorder):
    """
    Построение бинарного дерева по preorder и inorder обходам
    """
    # Хэш-таблица для быстрого поиска индексов в inorder
    inorder_index = {val: idx for idx, val in enumerate(inorder)}
    
    def build(pre_left, pre_right, in_left, in_right):
        """Рекурсивно строит дерево"""
        if pre_left > pre_right:
            return None
        
        # Корень - первый элемент preorder
        root_val = preorder[pre_left]
        root = TreeNode(root_val)
        
        # Находим индекс корня в inorder
        in_root_idx = inorder_index[root_val]
        
        # Размер левого поддерева
        left_size = in_root_idx - in_left
        
        # Рекурсивно строим поддеревья
        root.left = build(
            pre_left + 1, pre_left + left_size,
            in_left, in_root_idx - 1
        )
        root.right = build(
            pre_left + left_size + 1, pre_right,
            in_root_idx + 1, in_right
        )
        
        return root
    
    return build(0, len(preorder) - 1, 0, len(inorder) - 1)

73. Construct Binary Tree from Inorder and Postorder Traversal

Описание: Построить бинарное дерево по inorder и postorder обходам.

def buildTree(inorder, postorder):
    """
    Построение бинарного дерева по inorder и postorder обходам
    """
    inorder_index = {val: idx for idx, val in enumerate(inorder)}
    
    def build(in_left, in_right, post_left, post_right):
        """Рекурсивно строит дерево"""
        if in_left > in_right:
            return None
        
        # Корень - последний элемент postorder
        root_val = postorder[post_right]
        root = TreeNode(root_val)
        
        # Находим индекс корня в inorder
        in_root_idx = inorder_index[root_val]
        
        # Размер левого поддерева
        left_size = in_root_idx - in_left
        
        # Рекурсивно строим поддеревья
        root.left = build(
            in_left, in_root_idx - 1,
            post_left, post_left + left_size - 1
        )
        root.right = build(
            in_root_idx + 1, in_right,
            post_left + left_size, post_right - 1
        )
        
        return root
    
    return build(0, len(inorder) - 1, 0, len(postorder) - 1)

74. Populating Next Right Pointers in Each Node II

Описание: Заполнить указатели next в каждом узле для произвольного бинарного дерева.

class Node:
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

def connect(root):
    """
    Заполнение указателей next в каждом узле
    """
    if not root:
        return None
    
    # Используем BFS по уровням
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        prev = None
        
        for i in range(level_size):
            node = queue.popleft()
            
            if prev:
                prev.next = node
            prev = node
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        # Последний узел уровня указывает на None
    
    return root

# Решение с O(1) памяти
def connectConstantSpace(root):
    if not root:
        return None
    
    # Используем linked list подход
    dummy = Node(0)  # Dummy узел для начала каждого уровня
    current = root
    
    while current:
        tail = dummy  # Хвост linked list'а текущего уровня
        dummy.next = None  # Сбрасываем для нового уровня
        
        # Обходим текущий уровень
        while current:
            if current.left:
                tail.next = current.left
                tail = tail.next
            if current.right:
                tail.next = current.right
                tail = tail.next
            current = current.next
        
        # Переходим к следующему уровню
        current = dummy.next
    
    return root

75. Flatten Binary Tree to Linked List

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

def flatten(root):
    """
    Преобразование бинарного дерева в связный список (preorder)
    """
    if not root:
        return
    
    # Рекурсивно flatten поддеревья
    flatten(root.left)
    flatten(root.right)
    
    # Сохраняем правое поддерево
    right_subtree = root.right
    
    # Перемещаем левое поддерево вправо
    root.right = root.left
    root.left = None
    
    # Находим конец нового правого поддерева
    current = root
    while current.right:
        current = current.right
    
    # Присоединяем сохраненное правое поддерево
    current.right = right_subtree

# Итеративное решение
def flattenIterative(root):
    if not root:
        return
    
    stack = [root]
    prev = None
    
    while stack:
        node = stack.pop()
        
        if prev:
            prev.right = node
            prev.left = None
        
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
        
        prev = node

76. Path Sum

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

def hasPathSum(root, targetSum):
    """
    Проверка наличия пути от корня до листа с заданной суммой
    """
    if not root:
        return False
    
    # Если это лист, проверяем сумму
    if not root.left and not root.right:
        return root.val == targetSum
    
    # Рекурсивно проверяем левое и правое поддеревья
    new_target = targetSum - root.val
    return (hasPathSum(root.left, new_target) or 
            hasPathSum(root.right, new_target))

77. Sum Root to Leaf Numbers

Описание: Найти сумму всех чисел, образованных путями от корня до листьев.

def sumNumbers(root):
    """
    Сумма всех чисел, образованных путями от корня до листьев
    """
    def dfs(node, current_sum):
        if not node:
            return 0
        
        # Обновляем текущее число
        current_sum = current_sum * 10 + node.val
        
        # Если это лист, возвращаем число
        if not node.left and not node.right:
            return current_sum
        
        # Рекурсивно суммируем левое и правое поддеревья
        return dfs(node.left, current_sum) + dfs(node.right, current_sum)
    
    return dfs(root, 0)

78. Binary Tree Maximum Path Sum

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

def maxPathSum(root):
    """
    Максимальная сумма пути в бинарном дереве
    """
    max_sum = float('-inf')
    
    def dfs(node):
        nonlocal max_sum
        
        if not node:
            return 0
        
        # Рекурсивно вычисляем максимальные суммы левого и правого путей
        left_sum = max(dfs(node.left), 0)
        right_sum = max(dfs(node.right), 0)
        
        # Текущая сумма пути через этот узел
        current_path_sum = node.val + left_sum + right_sum
        
        # Обновляем глобальный максимум
        max_sum = max(max_sum, current_path_sum)
        
        # Возвращаем максимальную сумму пути, которая может быть продолжена
        return node.val + max(left_sum, right_sum)
    
    dfs(root)
    return max_sum

79. Binary Search Tree Iterator

Описание: Реализовать итератор для BST с next() и hasNext() за O(1) в среднем.

class BSTIterator:
    def __init__(self, root):
        """
        Инициализация итератора для BST
        """
        self.stack = []
        self._leftmost_inorder(root)
    
    def _leftmost_inorder(self, node):
        """
        Добавляет все левые узлы в стек
        """
        while node:
            self.stack.append(node)
            node = node.left
    
    def next(self):
        """
        Возвращает следующий наименьший элемент
        """
        if not self.hasNext():
            return -1
        
        node = self.stack.pop()
        
        # Если у узла есть правое поддерево, добавляем его
        if node.right:
            self._leftmost_inorder(node.right)
        
        return node.val
    
    def hasNext(self):
        """
        Проверяет, есть ли следующий элемент
        """
        return len(self.stack) > 0

80. Count Complete Tree Nodes

Описание: Подсчитать количество узлов в полном бинарном дереве за O(log n × log n).

def countNodes(root):
    """
    Подсчет узлов в полном бинарном дереве
    """
    if not root:
        return 0
    
    # Вычисляем высоту левого и правого поддеревьев
    left_height = get_left_height(root)
    right_height = get_right_height(root)
    
    # Если дерево идеально сбалансировано
    if left_height == right_height:
        return (1 << left_height) - 1  # 2^height - 1
    
    # Иначе рекурсивно считаем
    return 1 + countNodes(root.left) + countNodes(root.right)

def get_left_height(node):
    """Высота по левому краю"""
    height = 0
    while node:
        height += 1
        node = node.left
    return height

def get_right_height(node):
    """Высота по правому краю"""
    height = 0
    while node:
        height += 1
        node = node.right
    return height

81. Lowest Common Ancestor of a Binary Tree

Описание: Найти наименьшего общего предка двух узлов в бинарном дереве.

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

82. Binary Tree Right Side View

Описание: Вернуть значения узлов, видимых с правой стороны бинарного дерева.

def rightSideView(root):
    """
    Вид бинарного дерева справа
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        
        for i in range(level_size):
            node = queue.popleft()
            
            # Добавляем последний узел уровня
            if i == level_size - 1:
                result.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return result

83. Average of Levels in Binary Tree

Описание: Найти среднее значение для каждого уровня бинарного дерева.

def averageOfLevels(root):
    """
    Средние значения для каждого уровня бинарного дерева
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level_sum = 0
        
        for _ in range(level_size):
            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_size)
    
    return result

84. Binary Tree Level Order Traversal

Описание: Обход бинарного дерева по уровням (BFS).

def levelOrder(root):
    """
    Обход бинарного дерева по уровням
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level_nodes = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level_nodes.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level_nodes)
    
    return result

85. Binary Tree Zigzag Level Order Traversal

Описание: Z-образный обход бинарного дерева по уровням.

def zigzagLevelOrder(root):
    """
    Z-образный обход бинарного дерева по уровням
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    left_to_right = True
    
    while queue:
        level_size = len(queue)
        level_nodes = deque()
        
        for _ in range(level_size):
            node = queue.popleft()
            
            # Добавляем в зависимости от направления
            if left_to_right:
                level_nodes.append(node.val)
            else:
                level_nodes.appendleft(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(list(level_nodes))
        left_to_right = not left_to_right
    
    return result

86. Minimum Absolute Difference in BST

Описание: Найти минимальную абсолютную разницу между значениями в BST.

def getMinimumDifference(root):
    """
    Минимальная абсолютная разница в BST
    """
    prev_val = None
    min_diff = float('inf')
    
    def inorder(node):
        nonlocal prev_val, min_diff
        
        if not node:
            return
        
        inorder(node.left)
        
        # Вычисляем разницу с предыдущим значением
        if prev_val is not None:
            min_diff = min(min_diff, node.val - prev_val)
        
        prev_val = node.val
        
        inorder(node.right)
    
    inorder(root)
    return min_diff

87. Kth Smallest Element in a BST

Описание: Найти k-й наименьший элемент в BST.

def kthSmallest(root, k):
    """
    k-й наименьший элемент в BST
    """
    stack = []
    current = root
    count = 0
    
    while stack or current:
        # Идем до самого левого узла
        while current:
            stack.append(current)
            current = current.left
        
        # Извлекаем из стека
        current = stack.pop()
        count += 1
        
        if count == k:
            return current.val
        
        # Переходим к правому поддереву
        current = current.right
    
    return -1

88. Validate Binary Search Tree

Описание: Проверить, является ли бинарное дерево валидным BST.

def isValidBST(root):
    """
    Проверка, является ли дерево валидным BST
    """
    def validate(node, min_val, max_val):
        if not node:
            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'))

# Альтернативное решение с inorder обходом
def isValidBSTInorder(root):
    prev_val = None
    
    def inorder(node):
        nonlocal prev_val
        
        if not node:
            return True
        
        # Проверяем левое поддерево
        if not inorder(node.left):
            return False
        
        # Проверяем текущий узел
        if prev_val is not None and node.val <= prev_val:
            return False
        
        prev_val = node.val
        
        # Проверяем правое поддерево
        return inorder(node.right)
    
    return inorder(root)

89. Number of Islands

Описание: Подсчитать количество островов в бинарной матрице.

def numIslands(grid):
    """
    Подсчет количества островов (групп '1')
    """
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def dfs(i, j):
        """Обход острова в глубину"""
        if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] != '1':
            return
        
        # Помечаем ячейку как посещенную
        grid[i][j] = '0'
        
        # Рекурсивно посещаем соседей
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)
    
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)
    
    return count

90. Surrounded Regions

Описание: Захватить регионы, окруженные 'X'.

def solve(board):
    """
    Захват регионов, окруженных 'X'
    """
    if not board or not board[0]:
        return
    
    rows, cols = len(board), len(board[0])
    
    def dfs(i, j):
        """Помечаем незахваченные ячейки на границах"""
        if i < 0 or i >= rows or j < 0 or j >= cols or board[i][j] != 'O':
            return
        
        board[i][j] = 'E'  # Помечаем как крайний
        
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)
    
    # Помечаем 'O' на границах
    for i in range(rows):
        dfs(i, 0)
        dfs(i, cols - 1)
    
    for j in range(cols):
        dfs(0, j)
        dfs(rows - 1, j)
    
    # Преобразуем оставшиеся 'O' в 'X', а 'E' обратно в 'O'
    for i in range(rows):
        for j in range(cols):
            if board[i][j] == 'O':
                board[i][j] = 'X'
            elif board[i][j] == 'E':
                board[i][j] = 'O'

---

Ключевые моменты третьего блока:

1. Связные списки (61-67): Сложные операции (разворот частей, разделение, LRU)
2. Бинарные деревья (68-88): Рекурсия, обходы (DFS/BFS), свойства BST
3. Графы (89-90): Обход матриц как графов, алгоритмы поиска

Основные алгоритмы:

• Рекурсия и DFS для деревьев
• BFS для обхода по уровням
• Inorder обход для BST
• DFS на матрицах для поиска связных компонентов

Сложности:

• Деревья: O(n) время, O(h) память (высота дерева)
• Графы: O(rows × cols) время и память
• LRU Cache: O(1) для операций