Z30
Ağaçta Hırsız III
Teknik Tanım & Görev
Bir mahalledeki evler bir ikili ağaç şeklinde yerleşmiştir. Bir hırsız evleri soymak istemektedir ancak doğrudan birbirine bağlı (ebeveyn ile çocuk) iki ev aynı gece soyulursa güvenlik alarmı çalmaktadır. Yakalanmadan soyulabilecek EN FAZLA para miktarını hesaplayı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)
agacta_hirsiz(agac: list) -> intGirdi ve Çıktı Sözleşmesi
Çıktı Kuralı:Maksimum para miktarı.
Sistem Kısıtları (Constraints)
0 <= agac.length <= 10^4
0 <= agac[i] <= 10^4Örnek Yürütme Analizi
agac = [3, 2, 3, None, 3, None, 1]
3 (kök) + 3 + 1 = 7 (en iyi)
cevap: 7Örnek Test Senaryoları (3)
Örnek 1
Girdi:
[[3,2,3,null,3,null,1]]Beklenen Çıktı:
7Örnek 2: 4 + 5 = 9
Girdi:
[[3,4,5,1,3,null,1]]Beklenen Çıktı:
9Örnek 3: Boş
Girdi:
[[]]Beklenen Çıktı:
0