O37
En Düşük Ortak Ata - LCA
Teknik Tanım & Görev
Bir ikili ağaçta verilen iki farklı düğümün (p ve q) En Düşük Ortak Atasını (LCA) bulunuz. LCA; hem p'yi hem de q'yu torunu olarak barındıran en derin düğümdür (bir düğüm kendisinin de atası sayılabilir).
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)
en_dusuk_ortak_ata(agac: list, p: int, q: int) -> intGirdi ve Çıktı Sözleşmesi
Çıktı Kuralı:LCA düğümünün tam sayı değeri.
Sistem Kısıtları (Constraints)
2 <= agac.length <= 10^4
p != q ve ikisi de ağaçta mevcuttur
Tüm düğüm değerleri benzersizdirÖrnek Yürütme Analizi
agac = [3, 5, 1, 6, 2, 0, 8, None, None, 7, 4], p = 5, q = 1 -> LCA: 3
p = 5, q = 4 -> 4 düğümü 5'in torunudur -> LCA: 5Örnek Test Senaryoları (3)
Örnek 1
Girdi:
[[3,5,1,6,2,0,8,null,null,7,4],5,1]Beklenen Çıktı:
3Örnek 2: Kendisi Ata
Girdi:
[[3,5,1,6,2,0,8,null,null,7,4],5,4]Beklenen Çıktı:
5Örnek 3: İki Düğüm
Girdi:
[[1,2],1,2]Beklenen Çıktı:
1