0Pricing
Coding Interview Prep · Урок

k-й наименьший элемент, сумма диапазона и преобразование BST в отсортированный массив

Используйте отсортированный симметричный обход, чтобы найти k-й наименьший элемент за O(k) и сложить значения в диапазоне за O(log n + k)

«k-й наименьший элемент, сумма диапазона и преобразование BST в отсортированный массив» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.

k-е наименьшее значение в BST

Поиск k-го наименьшего элемента в BST (LeetCode #230) — классическая задача, напрямую использующая отсортированный порядок симметричного обхода. Поскольку симметричный обход посещает узлы в порядке возрастания, достаточно считать узлы во время обхода и вернуть значение при счётчике k. Временная сложность — O(h + k), где h — высота (для достижения крайнего левого узла), а k — количество шагов симметричного обхода.

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

def kth_smallest(root, k):
    count = [0]
    result = [None]

    def inorder(node):
        if not node or result[0] is not None:
            return
        inorder(node.left)
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        inorder(node.right)

    inorder(root)
    return result[0]

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_smallest(root, 1))  # 1
print(kth_smallest(root, 2))  # 2

Поиск k-го наименьшего: итеративный вариант со стеком

Итеративная версия использует шаблон симметричного обхода с явным стеком. Помещайте в стек левые узлы, пока не достигнете пустого указателя, затем извлекайте узел и увеличивайте счётчик. Когда счётчик достигнет k, верните значение текущего узла. Это позволяет избежать ограничения глубины рекурсии Python для очень глубоких деревьев; сложность остаётся O(h + k) по времени и O(h) по памяти. После рекурсивной версии интервьюеры часто просят написать итеративную.

def kth_smallest_iterative(root, k):
    stack = []
    curr = root
    count = 0
    while curr or stack:
        while curr:             # go as far left as possible
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()      # process node
        count += 1
        if count == k:
            return curr.val
        curr = curr.right       # move to right subtree
    return -1  # k out of range

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.left.left.left = TreeNode(1)
print(kth_smallest_iterative(root, 3))  # 3

k-е наибольшее значение в BST

Поиск k-го наибольшего значения использует обратный симметричный обход (право → корень → лево), который посещает узлы в убывающем порядке. Выполните k шагов и верните значение текущего узла. Это симметрично поиску k-го наименьшего и выполняется за O(h + k). В качестве альтернативы, если известен размер дерева, вычислите kth_smallest(root, total_count - k + 1), но вариант с обратным симметричным обходом элегантнее.

def kth_largest(root, k):
    count = [0]
    result = [None]

    def reverse_inorder(node):
        if not node or result[0] is not None:
            return
        reverse_inorder(node.right)   # visit LARGER values first
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        reverse_inorder(node.left)

    reverse_inorder(root)
    return result[0]

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_largest(root, 1))  # 4 (largest)
print(kth_largest(root, 2))  # 3 (2nd largest)

Сумма значений BST в диапазоне

Сумма значений BST в диапазоне (LeetCode #938) — задача на вычисление суммы всех значений из [low, high]. Используйте свойство BST для отсечения: если значение текущего узла меньше low, всё левое поддерево также находится ниже low — пропустите его. Если текущее значение больше high, пропустите правое поддерево. Такой подход отсекает много ветвей и эффективнее полного симметричного обхода.

def range_sum_bst(root, low, high):
    if not root:
        return 0
    total = 0
    if low <= root.val <= high:
        total += root.val
    if root.val > low:    # left subtree might have values >= low
        total += range_sum_bst(root.left, low, high)
    if root.val < high:   # right subtree might have values <= high
        total += range_sum_bst(root.right, low, high)
    return total

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(range_sum_bst(root, 7, 15))  # 7+10+15 = 32

Подсчёт узлов в диапазоне

Подсчёт узлов в диапазоне [low, high] использует ту же логику отсечения. Альтернативный вариант — применить bisect_left/правую границу к массиву симметричного обхода, но прямой обход BST занимает O(log n + k), тогда как предварительное преобразование в массив всегда занимает O(n). Выбирайте прямой обход, если только не требуется обрабатывать множество запросов по диапазону; в таком случае построение расширенного BST с количеством узлов в поддеревьях позволяет выполнять каждый запрос за O(log n).

def count_range(root, low, high):
    if not root:
        return 0
    count = 0
    if low <= root.val <= high:
        count += 1
    if root.val > low:
        count += count_range(root.left, low, high)
    if root.val < high:
        count += count_range(root.right, low, high)
    return count

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(count_range(root, 6, 15))  # 7, 10, 15 = 3

Преобразование BST в отсортированный массив: полный алгоритм

Преобразование BST в отсортированный массив занимает O(n) времени и O(n) памяти. Используйте симметричный обход и добавляйте каждое значение с помощью append. Это отправная точка для составных задач: «объединить два BST», «найти медиану BST» или «проверить, имеют ли два BST одинаковую последовательность симметричного обхода». Полученный массив поддерживает доступ по индексу за O(1), двоичный поиск и методы двух указателей, которые сам BST напрямую предоставить не может.

def bst_to_sorted(root):
    result = []
    def inorder(node):
        if not node:
            return
        inorder(node.left)
        result.append(node.val)
        inorder(node.right)
    inorder(root)
    return result

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
print(bst_to_sorted(root))  # [1, 3, 4, 5, 6, 8, 9]

# Binary search on the resulting sorted array:
import bisect
arr = bst_to_sorted(root)
print(bisect.bisect_left(arr, 6))   # 4 (index of 6)

Расширенное BST: размеры поддеревьев

Расширенное BST хранит в каждом узле дополнительную информацию, например размер его поддерева. Зная размеры поддеревьев, можно находить kth-smallest за O(log n): в каждом узле, если размер левого поддерева равен k-1, текущий узел является ответом; если размер левого поддерева не меньше k, рекурсивно переходим влево; в противном случае вычитаем размер левого поддерева и переходим вправо. Эта структура данных лежит в основе деревьев порядковой статистики, используемых в спортивном программировании.

class AugNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.size = 1  # subtree size

def get_size(node):
    return node.size if node else 0

def update_size(node):
    if node:
        node.size = 1 + get_size(node.left) + get_size(node.right)

def kth_smallest_aug(root, k):
    left_size = get_size(root.left)
    if k == left_size + 1:
        return root.val      # current node is kth
    elif k <= left_size:
        return kth_smallest_aug(root.left, k)
    else:
        return kth_smallest_aug(root.right, k - left_size - 1)

print('Augmented BST: O(log n) kth smallest with subtree sizes')

Поиск всех значений в BST между двумя узлами

Чтобы вернуть все значения строго между двумя узлами p и q (где p.val < q.val), объедините симметричный обход с отсечением за пределами диапазона: начинайте собирать значения после того, как пройдёте p.val, и остановитесь после q.val. Это обобщение подсчёта суммы в диапазоне, которое возвращает отсортированную последовательность между двумя искомыми значениями за O(h + k).

def values_between(root, low, high):
    result = []
    def inorder(node):
        if not node:
            return
        if node.val > low:    # might be values > low on left
            inorder(node.left)
        if low < node.val < high:  # strictly between
            result.append(node.val)
        if node.val < high:   # might be values < high on right
            inorder(node.right)
    inorder(root)
    return result

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.left = TreeNode(12)
root.right.right = TreeNode(18)
print(values_between(root, 6, 15))  # [7, 10, 12]

Медиана BST

Медиана BST — это среднее значение в результате симметричного обхода. Для n узлов медиана находится по индексу n // 2 (индексация с нуля). Можно собрать весь отсортированный массив и обратиться к элементу по этому индексу либо выполнить два прохода: сначала подсчитать n узлов, а затем во время второго симметричного обхода остановиться на узле с индексом n // 2. Другой вариант — использовать kth-smallest со значением k = n // 2 + 1.

def count_nodes(root):
    if not root:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

def median_of_bst(root):
    n = count_nodes(root)
    if n == 0:
        return None
    k = n // 2 + 1  # (n+1)/2-th element for odd, n/2+1-th for even
    return kth_smallest(root, k)

def kth_smallest(root, k):
    count = [0]; result = [None]
    def inorder(node):
        if not node or result[0] is not None: return
        inorder(node.left)
        count[0] += 1
        if count[0] == k: result[0] = node.val; return
        inorder(node.right)
    inorder(root); return result[0]

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
print(median_of_bst(root))  # 4 (middle of [1,3,4,5,8])

K ближайших к целевому значению элементов

Найдите k значений в BST, ближайших к целевому значению. Один из вариантов — преобразовать BST в отсортированный массив и использовать скользящее окно размера k. Другой вариант — использовать max-heap размера k: добавлять в него расстояния и извлекать элемент, когда размер превышает k. Подход с отсортированным массивом работает за O(n) и прост в реализации; подход с кучей работает за O(n log k), но подходит для обработки данных в потоковом режиме.

import heapq

def closest_k_values(root, target, k):
    # Collect sorted values
    arr = []
    def inorder(node):
        if not node: return
        inorder(node.left)
        arr.append(node.val)
        inorder(node.right)
    inorder(root)

    # Two-pointer sliding window of size k
    left, right = 0, k - 1
    while right < len(arr) - 1:
        if abs(arr[left] - target) <= abs(arr[right + 1] - target):
            break  # left is closer, don't advance
        left += 1
        right += 1
    return arr[left:right + 1]

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(closest_k_values(root, 3.7, 2))  # [3, 4]

Использование свойства порядка преемников

Многие задачи на BST сводятся к поиску следующего или предыдущего элемента в отсортированном порядке — эти операции выполняются за O(log n) с помощью навигации по BST. Созданный ранее итератор обеспечивает амортизированное время O(1) для перехода к следующему элементу. Объединив знания о kth-smallest, сумме в диапазоне и ближайшем значении, можно решить большинство задач на BST с собеседований, задав вопрос: «Как отсортированный порядок симметричного обхода упрощает эту задачу?» Этот универсальный шаблон служит ориентиром при решении задач на BST.

# Meta-pattern for BST problems:
# Step 1: What sorted-order property does this exploit?
# Step 2: Is in-order (ascending) or reverse in-order (descending) needed?
# Step 3: Can I prune using BST ordering to avoid O(n) scan?

# Quick reference:
# kth smallest  -> in-order, stop at kth node
# kth largest   -> reverse in-order, stop at kth node
# range sum     -> in-order + BST pruning
# closest value -> walk toward target, track best
# median        -> kth with k = n//2+1
# sorted array  -> full in-order
# validate      -> in-order prev check or min/max bounds
print('Sorted in-order is the universal BST problem tool')

Быстрая проверка

Проверьте своё понимание концепций структур данных и алгоритмов — подготовки к собеседованиям по программированию, рассмотренных в этом уроке.

Итоги урока

В этом уроке Вы научились находить kth smallest и largest с помощью симметричного и обратного симметричного обхода за O(h+k), вычислять сумму в диапазоне с отсечением в BST для эффективных запросов по диапазону, а также преобразовывать BST в отсортированный массив как основу алгоритмов на массивах. Далее мы изучим кучи и очереди с приоритетом.

Часто задаваемые вопросы

Урок «k-й наименьший элемент, сумма диапазона и преобразование BST в отсортированный массив» бесплатный?

Да — полный текст урока «k-й наименьший элемент, сумма диапазона и преобразование BST в отсортированный массив» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «k-й наименьший элемент, сумма диапазона и преобразование BST в отсортированный массив»?

Используйте отсортированный симметричный обход, чтобы найти k-й наименьший элемент за O(k) и сложить значения в диапазоне за O(log n + k) Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.

Сколько времени занимает урок «k-й наименьший элемент, сумма диапазона и преобразование BST в отсортированный массив»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Вставка и поиск в BST
  2. Удаление из BST: три случая
  3. Проверка BST и свойств симметричного обхода
  4. k-й наименьший элемент, сумма диапазона и преобразование BST в отсортированный массив
← Назад к Coding Interview Prep