O34
BST'de K'ıncı En Küçük Eleman
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) -> intGirdi 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