Z29
İkili Ağaç Maksimum Yol Toplamı
Teknik Tanım & Görev
Bir ikili ağaçtaki 'yol', her düğüm çifti arasında en fazla bir bağlantı kullanan kesintisiz düğüm dizisidir. Yol kökten geçmek zorunda değildir. Ağaçtaki olası tüm yollar arasında DÜĞÜM DEĞERLERİNİN TOPLAMI EN BÜYÜK olan yolun toplamını hesaplayınız (düğümler negatif değerler içerebilir).
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)
maksimum_yol_toplami(agac: list) -> intGirdi ve Çıktı Sözleşmesi
Çıktı Kuralı:Maksimum yol toplamı tam sayısı.
Sistem Kısıtları (Constraints)
1 <= agac.length <= 3 * 10^4
-1000 <= agac[i] <= 1000Örnek Yürütme Analizi
agac = [1, 2, 3] -> 2 + 1 + 3 = 6
agac = [-10, 9, 20, None, None, 15, 7] -> 15 + 20 + 7 = 42Örnek Test Senaryoları (3)
Örnek 1
Girdi:
[[1,2,3]]Beklenen Çıktı:
6Örnek 2: Köksüz Maksimum
Girdi:
[[-10,9,20,null,null,15,7]]Beklenen Çıktı:
42Örnek 3: Tek Negatif
Girdi:
[[-3]]Beklenen Çıktı:
-3