O34

BST'de K'ıncı En Küçük Eleman

Kıdemli Aday (Mid/Senior)
Hedef Süre: 25 - 35 Dakika
Tip: NUMERIC

Teknik Tanım & Görev

Düzey sıralı bir ikili arama ağacında k'ıncı en küçük düğümün İNDEKSİNİ döndürün (k 1-tabanlıdır). Biçim: Ağaç bir düğüm nesnesi olarak değil, düzey sırasıyla dizilmiş düz bir liste olarak verilir. Kök agac[0] konumundadır. i indeksindeki düğümün sol çocuğu 2*i+1, sağ çocuğu 2*i+2 indeksindedir. Olmayan çocuk null yazılır ve yer tutar; aradaki null silinirse indeksler kayar. null düğüm değildir. Boş ağaç [] ile verilir. BST kuralı: sol alt ağaçtaki her değer düğüm değerinden küçük veya eşittir; sağ alt ağaçtaki her değer düğüm değerinden büyüktür. Eşit değerler sola iner. Sıra, inorder (sol-kök-sağ) sırasıdır. Dönüş değer değil, o düğümün dizi indeksidir. sorted(değerler)[k-1] bir değer döndürür. Eşit değerlerde indekse göre kararlı sıralama da inorder ile aynı olmak zorunda değildir.

Fonksiyon İmzası (Python)

bst_k_en_kucuk(agac: list, k: int) -> int

Girdi ve Çıktı Sözleşmesi

Çıktı Kuralı:k'ıncı inorder düğümün 0-tabanlı heap indeksi.

Sistem Kısıtları (Constraints)

1 <= k <= düğüm sayısı <= 10^4
0 <= agac[i] <= 10^4 (null hariç)
Ağaç, yukarıdaki eşitlik kuralına uyan bir BST'dir

Örnek Yürütme Analizi

agac = [3, 1, 4, null, 2], k = 1
Inorder indeksleri: 1 (değer 1), 4 (değer 2), 0 (değer 3), 2 (değer 4)
k = 1 → indeks 1

agac = [2, 2, 3, 1], k = 2
        2
       / \
      2   3
     /
    1
Inorder: indeks 3 (1), indeks 1 (2), indeks 0 (2), indeks 2 (3)
k = 2 → indeks 1
Değere göre, eşitlikte küçük indeks öne alınarak sıralama k = 2 için indeks 0 verir; bu yanlıştır.

Örnek Test Senaryoları (4)

Örnek 1: k=1
Girdi:[[3,1,4,null,2],1]
Beklenen Çıktı:1
Örnek 2: k=3
Girdi:[[5,3,6,2,4,null,null,1],3]
Beklenen Çıktı:1
Örnek 3: Kök
Girdi:[[2,1,3],2]
Beklenen Çıktı:0
Örnek 4: Eşit Değer, Inorder İndeksi
Girdi:[[2,2,3,1],2]
Beklenen Çıktı:1
Python Editörü Yükleniyor...
Girdi Parametreleri
[
  [
    3,
    1,
    4,
    null,
    2
  ],
  1
]
Beklenen Çıktı
1