Z32
İkili Ağacı Düzleştirme
Teknik Tanım & Görev
Ağacı preorder sırasını koruyarak sağ omurgaya düzleştirin.
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.
Düzleştirme düğümlerin dizi indeksini değiştirmez. Her gerçek düğümün sol bağı kopar (-1) ve sağ bağı, preorder sırasındaki bir sonraki gerçek düğümün indeksine bağlanır. Son düğümün sağı -1'dir.
Dönüş [bas_indeks, baglar]. baglar[i], i. yuva null ise null; gerçek düğümse [sol, sag] = [-1, sonraki_indeks]. Preorder değer listesi bu yapıyı karşılamaz.
Fonksiyon İmzası (Python)
agaci_duzlestir(agac: list) -> listGirdi ve Çıktı Sözleşmesi
Çıktı Kuralı:[bas_indeks, baglar]. Boş ağaç [-1, []]. Tek düğüm [0, [[-1, -1]]].
Sistem Kısıtları (Constraints)
0 <= agac.length <= 2000
-100 <= değer <= 100 veya nullÖrnek Yürütme Analizi
agac = [1, 2, 5, 3, 4, null, 6]
İndeksler: 0:1, 1:2, 2:5, 3:3, 4:4, 5:null, 6:6
Preorder indeksleri: 0, 1, 3, 4, 2, 6
bas = 0
baglar[0] = [-1, 1]
baglar[1] = [-1, 3]
baglar[2] = [-1, 6]
baglar[3] = [-1, 4]
baglar[4] = [-1, 2]
baglar[5] = null
baglar[6] = [-1, -1]
Değer listesi [1, 2, 3, 4, 5, 6] bu bağı vermez.Örnek Test Senaryoları (3)
Örnek 1
Girdi:
[[1,2,5,3,4,null,6]]Beklenen Çıktı:
[0,[[-1,1],[-1,3],[-1,6],[-1,4],[-1,2],null,[-1,-1]]]Örnek 2: Boş
Girdi:
[[]]Beklenen Çıktı:
[-1,[]]Örnek 3: Tek Düğüm
Girdi:
[[0]]Beklenen Çıktı:
[0,[[-1,-1]]]