Z32

İkili Ağacı Düzleştirme

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

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

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