Binary Tree Level Order Traversal

Q: İkili Ağaçta Seviye Sıralı Gezinmenin zaman karmaşıklığı nedir?

Her iki çözüm de her düğümü bir kez ziyaret eder: n düğüm için O(n) zaman. Yanıt n değer içerir, dolayısıyla alan karmaşıklığı O(n) 'dir. Bunlara ek olarak kuyruk, yaklaşık olarak en geniş seviyedeki düğümleri; özyineleme ise ağacın yüksekliği kadar alan tutar.

Q: Genişlik öncelikli aramada bir seviyenin nerede bittiğini nasıl anlarsın?

Her turun başında kuyruğun boyutunu oku ve tam olarak o kadar düğüm al. İki başka yöntem de işe yarar: mevcut seviyeyi ve sonraki seviyeyi iki ayrı listede tutabilir ya da her seviyeden sonra kuyruğa bir işaretçi ekleyebilirsin.

Q: Dizi zaten düzey düzey saklanıyor. Neden onu dilimler hâlinde okumayalım?

Bu biçim için şu şekilde çalışır: kökü 0'da olan d düzeyindeki seviye, 2^d-1 ile 2^(d+1)-2 arasındaki indeksleri doldurur; bu nedenle bir aralıkta hiç değer kalmayana kadar her aralıktaki boş olmayan değerleri topla. Mülakatlarda genellikle bunun yerine işaretçileri olan düğüm nesneleri verilir ve bu biçime yalnızca kuyruk aktarılabilir.

OrtaAğaç dolaşma Kuyruk

+10

tree dizisi bir ikili ağaç tutar. Kök, 0 dizininde bulunur; i dizinindeki düğümün çocukları 2*i+1 (sol) ve 2*i+2 (sağ) dizinlerinde bulunur; -1 boş bir yeri belirtir ve sonunda fazladan -1 girdileri bulunabilir.

Düğüm değerlerini seviyelere göre döndür: kökten en derin seviyeye kadar her seviye için bir liste; her listedeki değerler soldan sağa sıralı olsun.

Fonksiyon

levelOrder(tree: integer-array) → integer-2d-array

treeinteger-array: yığın sırasındaki ağaç; boş bir yer için -1
Döndürürinteger-2d-array: her düzey için bir değer listesi; önce en üst düzey, her biri soldan sağa

Kısıtlar

1 ≤ tree.length ≤ 32767
Her tree[i], -1 ya da 0 ≤ tree[i] ≤ 1000 aralığında bir değerdir.
tree[0] hiçbir zaman -1 değildir, bu nedenle ağaçta en az bir düğüm vardır.
Dizi, son düğümden sonra fazladan -1 girdileriyle bitebilir.
Boş bir noktanın her iki çocuğu da boştur ve derinlik en fazla 14 olur.

Örnekler

Girdi: tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
Çıktı: [[4], [9, 2], [6, 8, 5], [3]]
Açıklama: 3. indeks boştur, bu nedenle 9 yalnızca sağ çocuğa, 6'ya sahiptir. Üçüncü seviyede 6, 8, 5 bulunur ve 9. indeksteki, 6'nın altındaki 3 dördüncü seviyede tek başınadır.

Girdi: tree = [7, -1, -1]
Çıktı: [[7]]
Açıklama: Kökün her iki çocuğu da -1 olduğundan, ağaç tek bir 7 düğümünden oluşur ve bir düzeyi vardır.

Girdi: tree = [1, 3, -1, 5, -1, -1, -1]
Çıktı: [[1], [3], [5]]
Açıklama: Her düğümün yalnızca bir sol çocuğu vardır: 1. indekste 3 ve 3. indekste 5. Her seviyede bir değer bulunur ve sondaki -1 girdileri hiçbir şey eklemez.

Ek soru

Düzeyleri, hiçbir düzeyi sıralamadan, ilkini soldan sağa, ikincisini sağdan sola ve bu şekilde sırayla olacak şekilde zikzak düzeninde döndürebilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Her seviye, soldan sağa kendi listesi olarak elde edilmelidir. Kuyruk kullanan bir genişlik öncelikli arama düğümleri bu sırayla ziyaret eder ve her turun başında kuyrukta tam olarak bir seviye bulunur; dolayısıyla kuyruk boyutu kaç düğüm alınacağını gösterir. Her düğümün derinliğini izleyen bir derinlik öncelikli dolaşım da işe yarar.

Derinlik öncelikli, derinliğe göre dosyalanmış

Sezgi

Ağacı derinlik öncelikli dolaşın, her düğüme derinliğini verin; kökün derinliği 0'dır ve her derinlik için bir liste tutun. d derinliğindeki bir düğüm, kendi değerini d listesine ekler; o seviyede görülen ilk düğümse listeyi oluşturur.

Her liste soldan sağa sıralanır, çünkü dolaşma, sağ alt ağaca geçmeden önce bir düğümün sol alt ağacını tamamlar. Aynı seviyedeki iki düğümden, yolların ayrıldığı noktada sola dönen yoldaki düğüme önce ulaşılır. 1. örnekte ziyaret sırası 4, 9, 6, 3, 2, 8, 5, [4], [9, 2], [6, 8, 5], [3] listelerini oluşturur.

Her düğüm bir kez ziyaret edilir: O(n) zaman; özyineleme ağacın derinliği kadar derine iner ve bu derinlik en fazla 14 seviyedir.

Algoritma

Düzeylerden oluşan boş bir liste oluşturun.
Kökü 0 derinliğinde ziyaret edin.
i düğümünde, derinlik d iken i dizinin sonunu geçmişse veya tree[i] değeri -1 ise durun.
Yalnızca d liste varsa boş bir liste ekleyin. tree[i] değerini d listesinin sonuna ekleyin.
Hem 2i+1 hem de 2i+2 düğümünü d+1 derinliğinde ziyaret edin.

def levelOrder(tree):
    n = len(tree)
    levels = []

    def visit(i, depth):
        if i >= n or tree[i] == -1:
            return
        if depth == len(levels):  # the first node seen on this level
            levels.append([])
        levels[depth].append(tree[i])
        # Left before right, so every level fills from left to right.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return levels

Genişlik öncelikli, her turda bir seviye

Sezgi

Bir düğümü kuyruktan çıkarıp çocuklarını, önce soldakini, kuyruğa ekle. d+1 düzeyindeki düğümler yalnızca d düzeyindekiler ayrılırken kuyruğa girer; böylece düğümler düzey düzey, soldan sağa kuyruktan çıkar.

Bu akışı düzeylere ayırmak için, turun başında kuyruğun boyutunu oku. Önceki düzey kuyruktan çıkmıştır ve sonraki düzeyden henüz hiçbir düğüm gelmemiştir; bu nedenle kuyrukta tam olarak geçerli düzey bulunur. Bu sayıda düğümü tek bir satıra al; çocukları sonraki turu bekler. Örnek 1'de turlarda sırasıyla 1, 2, 3 ve 1 düğüm alınır.

Her düğüm kuyruğa bir kez girip bir kez çıkar: O(n) zaman. Kuyruk yaklaşık bir düzey büyüklüğündedir; 14 düzeyli tam bir ağacın en derin düzeyinde en fazla 8,192 düğüm bulunur.

Algoritma

Kökün 0 indeksini kuyruğa ekle.
Kuyruk boş değilken boyutunu s oku ve boş bir satır başlat.
s adet indeksi çıkar. Her i indeksi için tree[i] değerini satıra ekle.
İndeks dizi sınırları içindeyse ve -1 değerini taşımıyorsa, önce 2i+1, ardından 2i+2 değerini kuyruğa ekle.
Satırı yanıta ekle ve sonraki tura başla.

from collections import deque


def levelOrder(tree):
    n = len(tree)
    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(tree[i])
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    queue.append(child)
        levels.append(row)
    return levels

Tuzaklar ve uç durumlar

Kuyruğu boşaltırken boyutunu okumak. while (j < queue.length) içinde, çocuklar geldikçe uzunluk artar; bu nedenle sonraki seviye geçerli satıra sızar.
Sol çocuktan önce sağ çocuğu eklemek veya önce sağ alt ağacı ziyaret etmek. Örnek 1'in ikinci seviyesi bu durumda [2, 9] olur.
child < n sınır denetimini atlamak. En derindeki düğümlerin çocukları dizinin sonunu aşar.
Düz bir dizi listesinin başından eleman çıkarmak; birçok dilde bu, kuyruğun tamamını her seferinde kaydırır. Gerçek bir kuyruk veya bir baş indeksi kullanın.
-1 değerini bir düğüm olarak ele almak. Bu değer hiçbir zaman bir satıra veya kuyruğa girmez: [7, -1, -1], [[7], []] değil, [[7]] sonucunu verir.

Sıkça sorulan sorular3

İkili Ağaçta Seviye Sıralı Gezinmenin zaman karmaşıklığı nedir?

Her iki çözüm de her düğümü bir kez ziyaret eder: n düğüm için O(n) zaman. Yanıt n değer içerir, dolayısıyla alan karmaşıklığı O(n)'dir. Bunlara ek olarak kuyruk, yaklaşık olarak en geniş seviyedeki düğümleri; özyineleme ise ağacın yüksekliği kadar alan tutar.

Genişlik öncelikli aramada bir seviyenin nerede bittiğini nasıl anlarsın?

Her turun başında kuyruğun boyutunu oku ve tam olarak o kadar düğüm al. İki başka yöntem de işe yarar: mevcut seviyeyi ve sonraki seviyeyi iki ayrı listede tutabilir ya da her seviyeden sonra kuyruğa bir işaretçi ekleyebilirsin.

Dizi zaten düzey düzey saklanıyor. Neden onu dilimler hâlinde okumayalım?

Bu biçim için şu şekilde çalışır: kökü 0'da olan d düzeyindeki seviye, 2^d-1 ile 2^(d+1)-2 arasındaki indeksleri doldurur; bu nedenle bir aralıkta hiç değer kalmayana kadar her aralıktaki boş olmayan değerleri topla. Mülakatlarda genellikle bunun yerine işaretçileri olan düğüm nesneleri verilir ve bu biçime yalnızca kuyruk aktarılabilir.

def levelOrder(tree):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]

Beklenen Çıktı

[[4], [9, 2], [6, 8, 5], [3]]