O37

En Düşük Ortak Ata - LCA

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

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

Girdi 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
Python Editörü Yükleniyor...
Girdi Parametreleri
[
  [
    3,
    5,
    1,
    6,
    2,
    0,
    8,
    null,
    null,
    7,
    4
  ],
  5,
  1
]
Beklenen Çıktı
3