Binary Tree Zigzag Level Order Traversal
Bir ikili ağaç, root dizisinde saklanıyor. Kök, 0 indeksinde bulunur; i indeksindeki düğümün çocukları 2*i+1 (sol) ve 2*i+2 (sağ) indekslerinde bulunur, -1 boş bir yeri belirtir ve dizinin sonunda fazladan -1 girdileri olabilir.
Düğüm değerlerini seviye seviye zikzak sırasıyla döndür: kökün seviyesini soldan sağa, sonraki seviyeyi sağdan sola ve en derin seviyeye kadar bu şekilde dönüşümlü olarak. Buna sarmal seviye sıralı dolaşım da denir.
Fonksiyon
- rootinteger-array
- yığın sırasındaki ağaç; boş bir yer için -1
- Döndürürinteger-2d-array
- her seviye için bir değer listesi; önce en üst seviye, soldan sağa ve sağdan sola dönüşümlü olarak
Kısıtlar
1 ≤ root.length ≤ 32767- Her
root[i],-1ya da0 ≤ root[i] ≤ 104koşulunu sağlayan bir değerdir. - Düğüm değerleri birbirinden farklıdır.
root[0]hiçbir zaman-1değildir, bu nedenle ağaçta en az bir düğüm vardır.- Dizi, son düğümden sonra fazladan
-1girdileriyle bitebilir. - Boş bir noktanın her iki çocuğu da boştur ve ağaç en fazla
14seviyelidir.
Örnekler
- Girdi
- root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
- Çıktı
- [[8], [5, 12], [1, 9, 14], [11, 2, 4]]
- Açıklama
- Soldan sağa okunduğunda seviyeler
8;12, 5;1, 9, 14;4, 2, 11şeklindedir. 1. ve 3. seviyeler ters yönde ilerler:[5, 12]ve[11, 2, 4].
- Girdi
- root = [1, 2, 3, 4, 5, 6, 7, -1, -1]
- Çıktı
- [[1], [3, 2], [4, 5, 6, 7]]
- Açıklama
- Üç seviyeli tam bir ağaç: orta seviye
[3, 2]olarak tersine döner ve üçüncü seviye tekrar soldan sağa ilerler. Sondaki iki-1girdisi,4düğümünün boş çocuk konumlarıdır.
- Girdi
- root = [5]
- Çıktı
- [[5]]
- Açıklama
- Tek bir düğüm, her iki yönde de okunabilen tek bir değerin bir düzeyidir.
Ek soru
Her değeri ters çevirmeden ve ikinci bir yığın kullanmadan satırındaki son yerine doğrudan koyabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Önce seviyeleri, düzey sıralı bir dolaşımda olduğu gibi soldan sağa topla. Bu listelerden hangilerinin değişmesi gerekiyor ve nasıl?
Seviyeleri kökten başlayarak 0'dan numaralandır. Tek seviyeler tersten okunur. Bir listeyi tersine çevirmek, onu okumak kadar maliyetlidir; bu nedenle bu seviyeleri tersine çevirmek, işlemin tamamının doğrusal kalmasını sağlar.
Tersine çevirmeyi atlamak için, geçerli seviyeyi bir yığında tutun ve elemanları çıkarırken çocuk düğümleri ikinci bir yığına ekleyin: soldan sağa okurken önce sol çocuk düğümü, sağdan sola okurken önce sağ çocuk düğümü. Böylece ikinci yığın, sonraki seviyeyi ihtiyaç duyduğunuz sırayla çıkarır.
Çözüm
Seviyeler, sıradan bir genişlik öncelikli aramadan elde edilir. Yeni olan kısım yöndür: her iki seviyeden biri ters çevrilmiş olarak çıkar. Ya satırları oluşturduktan sonra tek numaralı satırları ters çevir ya da her seviyeyi bir yığında tut; yığın, öğeleri ekleme sırasının tersine geri verir.
Önce seviyelere göre sırala, sonra her seviyeyi bir atlayarak ters çevir
Sezgi
Her turda bir seviyeyi işleyen bir kuyruk, her seviyeyi soldan sağa verir. Seviyeleri kökten başlayarak 0'dan numaralandırın: zikzak, tek seviyeleri sağdan sola okur; bu nedenle yalnızca bu satırları ters çevirmek sonucu verir.
Arama her düğümü bir kez ziyaret eder ve her ters çevirme her değere bir kez daha dokunur; dolayısıyla zaman karmaşıklığı O(n) olur.
Algoritma
0indeksli bir kuyrukla başlayın.- Her turda kuyruğun uzunluğunu
solarak kaydedin,sindeksi yeni bir satıra eklemek üzere kuyruktan çıkarın ve her birinin mevcut çocuklarını önce sol, sonra sağ olacak şekilde kuyruğa ekleyin. - Yanıt zaten tek sayıda satır içeriyorsa satırı ters çevirin.
- Satırı ekleyin ve kuyruk boşalana kadar devam edin.
from collections import deque
def zigzagLevelOrder(root):
n = len(root)
levels = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
row = []
for _ in range(len(queue)): # exactly the nodes of the current level
i = queue.popleft()
row.append(root[i])
for child in (2 * i + 1, 2 * i + 2):
if child < n and root[child] != -1:
queue.append(child)
if len(levels) % 2 == 1: # levels 1, 3, 5, ... read from right to left
row.reverse()
levels.append(row)
return levelsİki yığın
Sezgi
Mevcut düzeyi, düzeyin okunduğu yönde eleman çıkaran bir yığında tutun ve çıkarılan her düğümün çocuklarını ikinci bir yığına ekleyin. Mevcut yığın boşaldığında, ikinci yığında sonraki düzey bulunur.
Çalışmasını sağlayan, ekleme sırasıdır. Soldan sağa eleman çıkarırken her düğümün önce sol, sonra sağ çocuğunu ekleyin: en sağdaki düğümün sağ çocuğu en son eklenir, böylece sonraki düzey sağ ucundan çıkarılır. Sağdan sola eleman çıkarırken önce sağı, sonra solu ekleyin; en soldaki düğümün sol çocuğu en son eklenir.
Örnek 1: 8 değerini çıkarın, 12, 5 değerlerini ekleyin. 5, 12 değerlerini çıkarın, ardından 5 düğümünden 14 değerini ve 12 düğümünden 9, 1 değerlerini ekleyin. 1, 9, 14 değerlerini çıkarın, ardından 9 düğümünden 4, 2 değerlerini ve 14 düğümünden 11 değerini ekleyin. 11, 2, 4 değerlerini çıkarın.
Her düğüm bir kez eklenir ve bir kez çıkarılır: O(n) zaman, tersine çevirme adımı olmadan.
Algoritma
- Kökün indeksini
0bir yığına ekleyin ve soldan sağa okumaya başlayın. - Yığın boş değilken, her indeksi yeni bir satıra çıkarın ve çıkarılan her düğümün mevcut çocuklarını ikinci bir yığına ekleyin: soldan sağa okurken önce sol, sonra sağ; aksi hâlde önce sağ, sonra sol.
- Satırı yanıta ekleyin.
- İkinci yığını geçerli yığın yapın, yönü tersine çevirin ve tekrarlayın.
def zigzagLevelOrder(root):
n = len(root)
levels = []
current = [0] # a stack of node indexes; the root is never empty
left_to_right = True
while current:
row = []
upcoming = [] # the next level, pushed while this one pops
while current:
i = current.pop()
row.append(root[i])
# Push so that the next level pops out in its own direction.
if left_to_right:
children = (2 * i + 1, 2 * i + 2)
else:
children = (2 * i + 2, 2 * i + 1)
for child in children:
if child < n and root[child] != -1:
upcoming.append(child)
levels.append(row)
current = upcoming
left_to_right = not left_to_right
return levels
Tuzaklar ve uç durumlar
- Çocukların tek bir kuyruğa girme sırasını tersine çevirmek. Kardeşlerin sırası değişir, ancak ebeveynlerin sırası korunur: 1. örneğin üçüncü düzeyi
[9, 1, 14]olarak çıkar. - Düzeyleri 1'den başlayarak saymak. Her ters çevirme düzeyi bir eksik bırakır ve 1. örnek
[[8], [12, 5], [14, 9, 1], [4, 2, 11]]sonucunu verir. - İki yığınlı sürümün her düzeyinde aynı ekleme sırasını kullanmak. Böylece 1. örneğin üçüncü düzeyi yığından
[9, 1, 14]olarak çıkar. - Hâlâ eleman çıkardığınız yığına çocukları eklemek. Çocuklar, ebeveynlerinin düzeyinin geri kalanından önce çıkar.
- Bir satırı tersine çevirmek yerine sıralamak. 1. örneğin son düzeyi
[11, 2, 4]olmalıdır; hiçbir sıralama bunu vermez.
Sıkça sorulan sorular3
Zigzag dolaşımı ile seviye sırasına göre dolaşım arasındaki fark nedir?
Aynı seviyeleri, aynı düğümlerle ziyaret ederler. Seviye sıralaması her seviyeyi soldan sağa okur; zikzak sıralaması, kökün altındaki seviyeden başlayarak her ikinci seviyeyi sağdan sola okur. Her ikisi de O(n) zamanda çalışır.
Zigzag dolaşımı, bir ağacın spiral sıralı dolaşımıyla aynı mıdır?
Evet, bu iki ad aynı yürüyüşü tanımlar. Bazı metinlerde ikinci seviye sağdan değil soldan başlar; bu da yalnızca çevirmeleri bir seviye kaydırır. Burada kökün seviyesi soldan sağa, sonraki seviye ise sağdan sola ilerler.
Yılanvari seviye sıralaması bir çift uçlu kuyrukla yapılabilir mi?
Evet. Çift uçlu kuyruktaki her seviyeyi soldan sağa sırayla tutun. Soldan sağa ilerlenen bir seviyede düğümleri önden alın ve çocuklarını önce solu, sonra sağı gelecek şekilde arkaya ekleyin. Sağdan sola ilerlenen bir seviyede düğümleri arkadan alın ve çocuklarını önce sağı, sonra solu gelecek şekilde öne ekleyin. Tur başladığında aldığınız düğüm sayısı yine de seviyeyi belirler.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def zigzagLevelOrder(root):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
Beklenen Çıktı
[[8], [5, 12], [1, 9, 14], [11, 2, 4]]