Z33
İkili Ağaç Bölme ile Maksimum Çarpım
Teknik Tanım & Görev
Pozitif tamsayılardan oluşan bir ikili ağaçtan tam bir kenar silerek ağacı iki ayrı ağaca bölmek istiyorsunuz. Bu iki yeni ağacın düğüm toplamlarının çarpımının alabileceği EN BÜYÜK DEĞERİ bulunuz. Sonucu 1.000.000.007 modunda 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)
agac_bolme_maks_carpim(agac: list) -> intGirdi ve Çıktı Sözleşmesi
Çıktı Kuralı:Maksimum çarpım mod 1_000_000_007.
Sistem Kısıtları (Constraints)
2 <= agac.length <= 5 * 10^4
1 <= agac[i] <= 10^4Örnek Yürütme Analizi
agac = [1, 2, 3, 4, 5, 6]
toplam = 21
1-2 kenarı silinirse: alt ağaç [2, 4, 5] toplamı 11, kalanı 10 -> 11 * 10 = 110Örnek Test Senaryoları (3)
Örnek 1
Girdi:
[[1,2,3,4,5,6]]Beklenen Çıktı:
110Örnek 2: 6 * 4 = 24
Girdi:
[[1,null,2,null,null,3,4]]Beklenen Çıktı:
24Örnek 3
Girdi:
[[2,3,9,10,7,8,6,5,4,11,1]]Beklenen Çıktı:
1025