Binary Tree Level Order Traversal

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

Hem genişlik öncelikli hem de derinlik öncelikli çözüm her düğümü bir kez ziyaret eder; bu nedenle n düğüm için O(n) zamanda çalışırlar. Yanıtın kendisi n değer içerir, dolayısıyla alan karmaşıklığı O(n) 'dir. Bunun dışında kuyruk en fazla en geniş seviyedeki düğümler kadar eleman tutar, özyineleme ise en fazla ağacın yüksekliği kadar derine iner.

Q: Genişlik öncelikli aramada bir düzeyin nerede bittiğini nasıl anlarsınız?

Her turun başında kuyruğun boyutunu okuyun. O anda kuyruk, tam olarak bir seviyenin düğümlerini içerir; bu nedenle o kadar düğüm çıkarmak, yalnızca o seviyeyi çıkarır. İki başka yöntem de işe yarar: mevcut seviyeyi ve sonraki seviyeyi iki ayrı listede tutmak veya her seviyeden sonra bir işaretçi eklemek.

Q: Seviye sıralı dolaşım derinlik öncelikli aramayla yapılabilir mi?

Evet. Her düğüme derinliğini iletin ve değerini o derinliğe ait listeye ekleyin. Gezinme sol alt ağacı sağ alt ağaçtan önce ziyaret ettiği sürece, her liste soldan sağa sıralanır. Bu yöntem ayrıca O(n) karmaşıklığındadır; seviyeleri sıralı biçimde ürettiği için genişlik öncelikli gezinme daha doğrudan bir seçimdir.

Q: Dizi zaten seviye seviye saklanıyor. Neden onu dilimler halinde okumayalım?

Bu biçim için bu yöntem işe yarar: d düzeyi, 2^d-1 ile 2^(d+1)-2 indekslerini kapsar; bu yüzden her aralıktaki boş olmayan değerleri toplayıp hiçbir değer içermeyen ilk aralıkta durabilirsiniz. Ancak bir mülakatta ağaç genellikle, sol ve sağ işaretçileri olan ve dilimlenecek indeksleri bulunmayan düğüm nesneleri biçiminde verilir. Kuyruk tabanlı dolaşım, bu biçime ve zikzak sırası ya da sağdan görünüm gibi varyantlara da uyarlanabilir.

OrtaAğaç dolaşma Kuyruk

+10

tree dizisinde saklanan bir ikili ağaç veriliyor. 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 değerleri olabilir.

Düğüm değerlerini seviyelere göre döndürün: kökün değerini içeren bir liste, ardından bir alt seviyedeki değerleri soldan sağa içeren bir liste ve en derin seviyeye kadar bu şekilde devam edin.

Fonksiyon

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

treeinteger-array: yığın düzenindeki ağaç; boş bir yer için -1 kullanılır
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 yüzden 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: Kök 4, 1 ve 2 indekslerinde 9 ve 2 çocuklarına sahiptir. 3. indeks boştur, bu nedenle üçüncü seviyede önce 6 (4. indeks, 9'un altında), ardından 8 ve 5 (5. ve 6. indeksler, 2'nin altında) bulunur. 9. indeksteki 3, dördüncü seviyede tek başına duran 6'nın sol çocuğudur.

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

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: 3, 1. indekste ve 5, 3. indekste. Her seviyede bir değer bulunur ve sondaki -1 girdileri hiçbir şey eklemez.

Gönderirken +15 gizli test

Ek soru

Seviyeleri, herhangi bir seviyeyi sıralamadan; ilkini soldan sağa, ikincisini sağdan sola ve bu şekilde dönüşümlü olarak 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 sıralanmış ayrı bir liste olarak elde edilmelidir. Kuyruk kullanan bir genişlik öncelikli arama, düğümleri tam olarak bu sırayla ziyaret eder. Ek olarak bilinmesi gereken tek şey, bir seviyenin nerede bittiğidir: Her turun başında kuyrukta mevcut seviyenin tamamı ve başka hiçbir şey bulunmaz; bu nedenle boyutu, kaç düğüm alınacağını gösterir. Her düğümün derinliğini izlediği ve önce sola, sonra sağa gittiği sürece derinlik öncelikli dolaşma da işe yarar.

Derinliğe göre sıralanmış derinlik öncelikli

Sezgi

Önce dizi içinde gezinmeyi ele alalım. i indeksindeki düğümün sol çocuğu 2i+1, sağ çocuğu ise 2i+2 indeksindedir. İndeksi dizinin sonunu aşan veya -1 değerini içeren bir çocuk yoktur. 1. örnekte 9 düğümünün (indeks 1) çocukları 3 ve 4 indekslerindedir; bu indekslerde sırasıyla -1 ve 6 bulunduğundan 9 düğümünün yalnızca sağ çocuğu vardır.

Şimdi ağaçta derinlik öncelikli dolaşın ve her düğüme derinliğini iletin; kökün derinliği 0'dır. Her derinlik için bir liste tutun. Derinliği d olan bir düğüme ulaştığınızda değerini d listesine ekleyin; o ana kadar yalnızca d liste varsa bu, yeni bir seviyedeki ilk düğümdür, dolayısıyla önce yeni bir liste oluşturun.

Her seviye neden soldan sağa sıralanır? Dolaşma, sağ alt ağaca geçmeden önce bir düğümün sol alt ağacının tamamını bitirir. Aynı seviyedeki iki düğümü ele alalım: kökten gelen yollarının ayrıldığı noktada biri sola, diğeri sağa gider ve dolaşma önce soldakine ulaşır. 1. örnekte sıralama 4, 9, 6, 3, 2, 8, 5 şeklindedir; bu da listeleri [4], [9, 2], [6, 8, 5], [3] olarak doldurur.

Her düğüm bir kez ziyaret edilir; bu nedenle n düğüm için zaman karmaşıklığı O(n)'dir ve listeler toplam n değer içerir. Özyineleme yalnızca ağacın derinliği kadar derine iner; burada en fazla 15 seviyedir. R sürümü bunun yerine açık bir yığın kullanır; önce sağ çocuğu, sonra sol çocuğu yığına ekler, böylece önce sol çocuk çıkar. Ardından değerleri derinliklerine göre split ile gruplar.

Algoritma

Boş bir seviye listesi oluştur.
Kökü 0 derinliğiyle ziyaret et.
i düğümünde, derinlik d iken, i dizinin sonunu geçmişse veya tree[i] değeri -1 ise dur.
Yalnızca d liste varsa, boş bir liste ekle. tree[i] değerini d numaralı listeye ekle.
Önce 2i+1, ardından 2i+2 düğümünü, her ikisini de d+1 derinliğiyle ziyaret et.

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 kuyruk, değerleri kuyruğa girdikleri sırayla geri verir. Kökü kuyruğa ekle. Ardından sırayla bir düğümü kuyruktan çıkarıp çocuklarını ekle; önce sol çocuk. d düzeyindeki ebeveyni kuyruktan çıkarıldığında d+1 düzeyindeki her düğüm kuyruğa girer; bu nedenle d düzeyindeki tüm düğümler, d+1 düzeyindeki herhangi bir düğümden önce çıkar ve aynı düzeydeki düğümler soldan sağa çıkar.

Böylece değerlerden oluşan tek bir düzey sıralı akış elde edilir. Bu akışı düzeylere ayırmak için bir turun başında kuyruğun boyutunu oku. O anda kuyrukta tam olarak mevcut düzey bulunur: önceki düzey bitmiştir ve sonraki düzeyden henüz hiçbir düğüm gelmemiştir. Bu sayıda düğümü çıkarıp tek bir listeye koy. Ekledikleri çocuklar bir sonraki tura aittir.

1. örnekte kuyruk [4] olarak başlar: 1 düğüm çıkar, satır [4] olur ve 9, 2 kuyruğa girer. 2 düğüm çıkar, satır [9, 2] olur ve 6, 8, 5 kuyruğa girer. 3 düğüm çıkar, satır [6, 8, 5] olur ve 3 kuyruğa girer. 1 düğüm çıkar, satır [3] olur ve kuyruk boşalır.

Her düğüm kuyruğa bir kez girip kuyruktan bir kez çıktığı için süre O(n) olur. Kuyruk en fazla yaklaşık bir düzey kadar düğüm tutar; derinliği 14 olan tam bir ağacın en derin düzeyinde bu sayı 16384'e kadar çıkar. Gerçek bir kuyruk ya da bir baş indeksi kullan: birçok dilde düz bir dizi listesinden ilk öğeyi çıkarmak, sonrasındaki tüm öğeleri kaydırır.

Algoritma

Kökün indeksini 0 kuyruğa ekle.
Kuyruk boş değilken, uzunluğunu s olarak oku ve boş bir satır başlat.
s indeks çıkar. Her i indeksi için tree[i] değerini satıra ekle.
İndeks dizi içindeyse ve -1 değerini taşımıyorsa, önce 2i+1 değerini, 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

Gezinmenin kendisi kısadır. Hatalar, seviye sınırlarında ve boş konumlardadır.

Kuyruğu hâlâ boşaltırken kuyruğun boyutunu okumak. while (j < queue.length) gibi bir döngüde çocuklar geldikçe uzunluk artar, bu yüzden sonraki seviye mevcut satıra sızar. Tur başlamadan önce boyutu bir kez okuyun.
Sol çocuktan önce sağ çocuğu eklemek. Böylece her seviye sağdan sola çıkar. Aynı durum, önce sağ alt ağacı ziyaret eden derinlik öncelikli gezinme için de geçerlidir.
-1 değerini bir değer olarak ele almak. Boş bir konum düğüm değildir; bu yüzden hiçbir zaman bir satıra ya da kuyruğa girmez.
Sınır kontrolünü unutmak. En derindeki düğümlerin çocukları dizinin sonundan sonraki konumlarda olabilir; bu nedenle tree[child] değerini okumadan önce child < n koşulunu kontrol edin.
Boş seviyeler döndürmek. Sondaki -1 girdileri düğüm içermez; bu nedenle [7, -1, -1] için yanıt [[7]] olur, [[7], []] değil.

Sıkça sorulan sorular4

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

Hem genişlik öncelikli hem de derinlik öncelikli çözüm her düğümü bir kez ziyaret eder; bu nedenle n düğüm için O(n) zamanda çalışırlar. Yanıtın kendisi n değer içerir, dolayısıyla alan karmaşıklığı O(n)'dir. Bunun dışında kuyruk en fazla en geniş seviyedeki düğümler kadar eleman tutar, özyineleme ise en fazla ağacın yüksekliği kadar derine iner.

Genişlik öncelikli aramada bir düzeyin nerede bittiğini nasıl anlarsınız?

Her turun başında kuyruğun boyutunu okuyun. O anda kuyruk, tam olarak bir seviyenin düğümlerini içerir; bu nedenle o kadar düğüm çıkarmak, yalnızca o seviyeyi çıkarır. İki başka yöntem de işe yarar: mevcut seviyeyi ve sonraki seviyeyi iki ayrı listede tutmak veya her seviyeden sonra bir işaretçi eklemek.

Seviye sıralı dolaşım derinlik öncelikli aramayla yapılabilir mi?

Evet. Her düğüme derinliğini iletin ve değerini o derinliğe ait listeye ekleyin. Gezinme sol alt ağacı sağ alt ağaçtan önce ziyaret ettiği sürece, her liste soldan sağa sıralanır. Bu yöntem ayrıca O(n) karmaşıklığındadır; seviyeleri sıralı biçimde ürettiği için genişlik öncelikli gezinme daha doğrudan bir seçimdir.

Dizi zaten seviye seviye saklanıyor. Neden onu dilimler halinde okumayalım?

Bu biçim için bu yöntem işe yarar: d düzeyi, 2^d-1 ile 2^(d+1)-2 indekslerini kapsar; bu yüzden her aralıktaki boş olmayan değerleri toplayıp hiçbir değer içermeyen ilk aralıkta durabilirsiniz. Ancak bir mülakatta ağaç genellikle, sol ve sağ işaretçileri olan ve dilimlenecek indeksleri bulunmayan düğüm nesneleri biçiminde verilir. Kuyruk tabanlı dolaşım, bu biçime ve zikzak sırası ya da sağdan görünüm gibi varyantlara da uyarlanabilir.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

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

Beklenen

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