0Pricing
Coding Interview Prep · Lekcja

K-ty najmniejszy element, suma zakresu i BST do posortowanej tablicy

Wykorzystają Państwo posortowane przejście inorder, aby znaleźć k-ty najmniejszy element w O(k) i zsumować wartości w zakresie w O(log n + k).

K-ty najmniejszy element, suma zakresu i BST do posortowanej tablicy to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

K-ty najmniejszy element w BST

Kth Smallest Element in a BST (LeetCode #230) to klasyczne zadanie, które bezpośrednio wykorzystuje posortowaną kolejność przejścia inorder. Ponieważ przejście inorder odwiedza węzły w kolejności rosnącej, wystarczy zliczać odwiedzane węzły i zwrócić wartość, gdy licznik osiągnie k. Złożoność czasowa wynosi O(h + k), gdzie h oznacza wysokość drzewa (potrzebną do dotarcia do najbardziej lewego węzła), a k — liczbę kroków przejścia inorder.

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-ty najmniejszy: wersja iteracyjna ze stosem

Wersja iteracyjna korzysta ze wzorca przejścia inorder z jawnym stosem. Należy odkładać na stos lewe węzły aż do napotkania null, a następnie zdejmować je ze stosu i zliczać. Gdy licznik osiągnie k, należy zwrócić wartość bieżącego węzła. Pozwala to uniknąć limitu rekurencji języka Python w przypadku bardzo głębokich drzew i zapewnia złożoność czasową O(h + k) oraz pamięciową O(h). Osoby prowadzące rozmowy kwalifikacyjne często proszą o wersję iteracyjną po przedstawieniu wersji rekurencyjnej.

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-ty największy element w BST

Kth Largest korzysta z odwrotnego przejścia inorder (prawe poddrzewo → korzeń → lewe poddrzewo), które odwiedza węzły w kolejności malejącej. Należy wykonać k kroków i zwrócić wartość bieżącego węzła. Jest to odpowiednik znajdowania k-tego najmniejszego elementu i ma złożoność czasową O(h + k). Alternatywnie, jeśli znany jest rozmiar drzewa, można obliczyć kth_smallest(root, total_count - k + 1), ale podejście z odwrotnym przejściem inorder jest bardziej eleganckie.

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)

Suma wartości w zakresie BST

Range Sum of BST (LeetCode #938) wymaga obliczenia sumy wszystkich wartości z zakresu [low, high]. Należy wykorzystać własność BST do przycinania: jeśli wartość bieżącego węzła jest mniejsza niż low, całe lewe poddrzewo również znajduje się poniżej low — należy je pominąć. Jeśli bieżąca wartość jest większa niż high, należy pominąć prawe poddrzewo. Pozwala to przyciąć wiele gałęzi i jest wydajniejsze niż pełne przejście inorder.

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

Zliczanie węzłów w zakresie

Zliczanie węzłów z zakresu [low, high] opiera się na tej samej logice przycinania. Alternatywnie można użyć bisect_left/bisect_right na tablicy inorder — jednak bezpośrednie przejście po BST ma złożoność O(log n + k), podczas gdy wcześniejsza konwersja do tablicy zawsze wymaga O(n). Należy wybrać bezpośrednie przejście, chyba że trzeba obsługiwać wiele zapytań o zakres; w takim przypadku zbudowanie rozszerzonego BST z licznikami w poddrzewach umożliwia obsługę każdego zapytania w czasie 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 do posortowanej tablicy: pełny algorytm

Konwersja BST do posortowanej tablicy ma złożoność czasową O(n) i pamięciową O(n). Należy wykonać przejście inorder i dodać każdą wartość do tablicy. Jest to punkt wyjścia dla wieloetapowych zadań, takich jak „scalanie dwóch BST”, „znalezienie mediany BST” lub „sprawdzenie, czy dwa BST mają tę samą sekwencję inorder”. Wynikowa tablica zapewnia dostęp do elementu po indeksie w czasie O(1), wyszukiwanie binarne oraz techniki dwóch wskaźników, których samo BST nie może bezpośrednio zapewnić.

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)

Rozszerzone BST: rozmiary poddrzew

Rozszerzone BST przechowuje w każdym węźle dodatkowe informacje, takie jak rozmiar jego poddrzewa. Dzięki rozmiarom poddrzew znalezienie k-tego najmniejszego elementu ma złożoność O(log n): w każdym węźle, jeśli rozmiar lewego poddrzewa wynosi k-1, bieżący węzeł jest szukanym elementem; jeśli rozmiar lewego poddrzewa jest większy lub równy k, należy przejść rekurencyjnie w lewo; w przeciwnym razie pomniejszyć k i przejść w prawo. To struktura danych stanowiąca podstawę drzew statystyk pozycyjnych używanych w programowaniu konkursowym.

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')

Znajdowanie wszystkich wartości w BST między dwoma węzłami

Aby zwrócić wszystkie wartości znajdujące się ściśle między dwoma węzłami p i q (gdzie p.val < q.val), należy połączyć przejście inorder z przycinaniem zakresu: rozpocząć zbieranie wartości po przekroczeniu p.val i zakończyć po przekroczeniu q.val. Jest to uogólnienie sumy z zakresu, które w czasie O(h + k) zwraca posortowaną sekwencję wartości znajdujących się między dwiema wartościami zapytania.

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]

Mediana BST

Mediana BST to środkowa wartość w przejściu inorder. Dla n węzłów mediana znajduje się pod indeksem n // 2 (indeksowanie od zera). Można zebrać całą posortowaną tablicę i odczytać z niej wartość pod odpowiednim indeksem albo wykonać dwa przejścia: najpierw policzyć n węzłów, a następnie podczas drugiego przejścia inorder zatrzymać się na węźle o indeksie n // 2. Alternatywnie można znaleźć k-ty najmniejszy element, przyjmując 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 najbliższych wartości względem wartości docelowej

Należy znaleźć k wartości w BST, które są najbliższe wartości docelowej. Jedno z podejść wykorzystuje dwa wskaźniki: najpierw konwertuje BST na posortowaną tablicę, a następnie korzysta z przesuwanego okna o rozmiarze k. Alternatywnie można użyć kopca maksymalnego o rozmiarze k, do którego wstawia się odległości, a następnie usuwa element, gdy rozmiar przekroczy k. Podejście z posortowaną tablicą ma złożoność czasową O(n) i jest proste, natomiast podejście z kopcem ma złożoność O(n log k), ale działa w kontekście strumieniowym.

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]

Wykorzystanie własności następnika w kolejności

Wiele problemów dotyczących BST sprowadza się do znalezienia następnego lub poprzedniego elementu w kolejności sortowania — operacji, które dzięki nawigacji po BST mają złożoność O(log n). Zbudowany wcześniej iterator zapewnia zamortyzowaną złożoność O(1) operacji next. Łącząc wiedzę o k-tym najmniejszym elemencie, sumie z zakresu i znajdowaniu najbliższej wartości, można rozwiązać większość zadań rekrutacyjnych dotyczących BST, zadając sobie pytanie: „Jak uporządkowanie wynikające z przejścia inorder upraszcza to zadanie?”. Ten metawzorzec jest kompasem rozwiązywania problemów z 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')

Szybkie sprawdzenie

Proszę sprawdzić zrozumienie zagadnień Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.

Podsumowanie lekcji

W tej lekcji omówiono: znajdowanie k-tego najmniejszego i k-tego największego elementu za pomocą przejścia inorder i odwrotnego przejścia inorder w czasie O(h+k), sumę z zakresu z przycinaniem BST w celu wydajnego obsługiwania zapytań zakresowych oraz konwersję BST na posortowaną tablicę jako podstawę algorytmów tablicowych. Następnie omówimy kopce i kolejki priorytetowe.

Często zadawane pytania

Czy lekcja „K-ty najmniejszy element, suma zakresu i BST do posortowanej tablicy” jest bezpłatna?

Tak — pełny tekst „K-ty najmniejszy element, suma zakresu i BST do posortowanej tablicy” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „K-ty najmniejszy element, suma zakresu i BST do posortowanej tablicy”?

Wykorzystają Państwo posortowane przejście inorder, aby znaleźć k-ty najmniejszy element w O(k) i zsumować wartości w zakresie w O(log n + k). Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.

Ile czasu zajmuje lekcja „K-ty najmniejszy element, suma zakresu i BST do posortowanej tablicy”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Wstawianie i wyszukiwanie w BST
  2. Usuwanie z BST: trzy przypadki
  3. Sprawdzanie BST i właściwości inorder
  4. K-ty najmniejszy element, suma zakresu i BST do posortowanej tablicy
← Powrót do Coding Interview Prep