O41
BST Iterator Simülasyonu
Teknik Tanım & Görev
Bir İkili Arama Ağacı üzerinde in-order (artan sıra) dolaşım yapan bir Iterator tasarlayınız. 'next' çağrısı ağaçtaki sıradaki en küçük sayıyı döndürür. 'hasNext' ise sırada okunacak düğüm kalıp kalmadığını (boolean) bildirir. Verilen işlem listesini sırayla çalıştırıp çıktıları döndürünüz.
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.
Fonksiyon İmzası (Python)
bst_iterator_islemleri(agac: list, islemler: list[str]) -> listGirdi ve Çıktı Sözleşmesi
Çıktı Kuralı:Sorgu sonuçları listesi (sayı veya boolean).
Sistem Kısıtları (Constraints)
1 <= agac.length <= 10^4
İşlemler: 'next' ve 'hasNext'
next() çağrıları her zaman geçerli bir eleman varken yapılırÖrnek Yürütme Analizi
agac = [7, 3, 15, None, None, 9, 20]
islemler = ['next', 'next', 'hasNext', 'next', 'hasNext']
cevap: [3, 7, True, 9, True]Örnek Test Senaryoları (3)
Örnek 1
Girdi:
[[7,3,15,null,null,9,20],["next","next","hasNext","next","hasNext"]]Beklenen Çıktı:
[3,7,true,9,true]Örnek 2
Girdi:
[[5],["hasNext","next","hasNext"]]Beklenen Çıktı:
[true,5,false]Örnek 3
Girdi:
[[3,1,4],["next","next","next","hasNext"]]Beklenen Çıktı:
[1,3,4,false]