Invert Binary Tree

+10

Seviye sırasına göre dizide saklanan bir ikili ağaç alıyorsun: tree. 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.

Ağacı tersine çevir: Her düğümün sol ve sağ çocuklarını değiştir, böylece ağacın tamamı ayna görüntüsü hâline gelsin. Tersine çevrilmiş ağacı aynı biçimde, sonunda hiç -1 girdisi olmayacak şekilde döndür.

Fonksiyon

invertTree(tree: integer-array) → integer-array

treeinteger-array: ikili ağacı düzey sırasına göre, boş bir yer için -1 kullanarak
Döndürürinteger-array: sonunda -1 girişleri olmadan, seviyelere göre aynalanmış ağaç

Kısıtlar

1 ≤ tree.length ≤ 16383
Her tree[i], -1 ya da 0 ≤ tree[i] ≤ 1000 koşulunu sağlayan bir değerdir.
tree[0] hiçbir zaman -1 değildir; bu nedenle tree'de 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 = [5, 3, 8, 1, 4, -1, 9]
Çıktı: [5, 8, 3, 9, -1, 4, 1]
Açıklama: Kökün çocukları olan 3 ve 8 yer değiştirir. Bunların altında, 3'ün altındaki 1 ve 4, 4 ve 1 olarak geri gelir; yalnızca sağ çocuğu 9 olan 8'in ise artık bu çocuğu solundadır.

Girdi: tree = [2, 7, -1, 6]
Çıktı: [2, -1, 7, -1, -1, -1, 6]
Açıklama: 2, 7, 6 zinciri sola eğilir ve aynadaki görüntüsü sağa eğilir. 7, 1 indeksinden 2 indeksine; 6 ise 3 indeksinden 6 indeksine taşınır. Bu nedenle yanıt girdiden daha uzundur ve son düğümden önceki her boş konumda -1 bulunur.

Girdi: tree = [1, -1, -1]
Çıktı: [1]
Açıklama: Tek bir düğüm kendi aynasıdır. İki -1 girdisi dolgu değeridir ve sonuç sondaki tüm -1 değerlerini çıkarır.

Ek soru

Ağacın ters çevrilmiş bir kopyasını oluşturmadan, aynı indeks çiftlerini kullanarak kendi aynadaki yansıması olup olmadığını nasıl kontrol edersin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Bir ağacı yansıtmak, her düğümün sol ve sağ alt ağacını en alt seviyeye kadar yer değiştirmek demektir. Düğüm nesneleriyle bu, her düğüm için bir yer değiştirme işlemidir. Bu dizi gösteriminde bir düğümün yeri, onun indeksidir; dolayısıyla iki alt ağacı yer değiştirmek, bunların içindeki her düğümü taşımak anlamına gelir. Çözüm, yanıtı yeni bir dizide oluşturup her düğümü doğrudan yansıtılmış indeksine kopyalamak ve gezinme sırasında indeks çiftlerini taşımaktır: düğümün şu an bulunduğu yer ve gideceği yer.

Her düğümü simetrik indeksine yerleştiren özyineleme

Sezgi

Önce, dizi içinde nasıl gezinileceğine bakalım. i indeksindeki düğümün sol çocuğu 2*i+1, sağ çocuğu ise 2*i+2 indeksindedir. Bir çocuk ancak indeksi dizinin içindeyse ve o konumdaki değer -1 değilse gerçektir. [5, 3, 8, 1, 4, -1, 9] dizisinde kök 5'in 1 ve 2 indekslerinde 3 ve 8 çocukları vardır; 2 indeksindeki 8'in 5 indeksinde boş bir sol konumu, 6 indeksinde ise 9 çocuğu vardır.

Şimdi yansıtma işlemine bakalım. Kök 0 indeksinde kalır. Bir düğümün sol alt ağacı, yansıtılmış kopyasının sağ alt ağacı; sağ alt ağacı ise sol alt ağacı olur. Dolayısıyla src indeksindeki düğüm, sonuçta dst indeksine yerleşiyorsa sol çocuğu 2*dst+2, sağ çocuğu ise 2*dst+1 indeksine yerleşir. place(src, dst) fonksiyonunu yaz: değeri kopyala, ardından place(2*src+1, 2*dst+2) ve place(2*src+2, 2*dst+1) çağrılarını yap. Boş bir konuma ulaşıldığında hemen geri dön. İlk örnekte 1 indeksindeki 3, 2 indeksine yerleşir; dolayısıyla sol çocuğu 1, 6 indeksine, sağ çocuğu 4 ise 5 indeksine yerleşir.

Bir düğümün seviyesi hiçbir zaman değişmez; bu nedenle yansıtılmış indeksi de öncekiyle aynı seviyede kalır. Uzunluğu tam seviyelere (1, 3, 7, 15, ...) yukarı yuvarla, bu kadar yeri -1 ile doldur ve sonunda sondaki -1 değerlerini kaldır. İkinci örnekte 4 uzunluğu yukarı yuvarlanarak 7 olur; böylece 6 indeksindeki 6 için yer açılır.

Her düğüm bir kez yerleştirilir; çıktı bir kez doldurulup kısaltılır. n uzunluğundaki bir dizi için zaman karmaşıklığı O(n)'dir. Çıktı O(n) bellek, çağrı yığını ise O(h) alan kullanır; burada en fazla 14 çağrı çerçevesi vardır. Bu problemde özyinelemeyi güvenli kılan da budur.

Algoritma

Uzunluğu size = 2^k - 1 olacak şekilde yukarı yuvarlayın ve bu boyutta bir çıktıyı -1 ile doldurun.
place(src, dst) yazın: src sonu geçmişse veya tree[src] değeri -1 ise geri dönün.
Aksi takdirde out[dst] = tree[src] atamasını yapın, ardından place(2*src+1, 2*dst+2) ve place(2*src+2, 2*dst+1) çağrılarını yapın.
place(0, 0) çağrısını yapın, sondaki -1 girdilerini kaldırın ve çıktıyı döndürün.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size

    def place(src, dst):
        if src >= n or tree[src] == -1:
            return
        out[dst] = tree[src]
        place(2 * src + 1, 2 * dst + 2)  # the left subtree goes to the right
        place(2 * src + 2, 2 * dst + 1)  # the right subtree goes to the left

    place(0, 0)
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

İndeks çiftlerinden oluşan bir kuyrukla genişlik öncelikli arama

Sezgi

Aynı çiftler özyineleme olmadan da çalışır. Kuyruğa (0, 0) ekleyin: kök ve gideceği yer. Önden bir (src, dst) çifti alın, tree[src] değerini out[dst] konumuna kopyalayın ve her gerçek çocuğu hedefi yer değiştirmiş hâliyle kuyruğa ekleyin: sol çocuk 2*src+1 için 2*dst+2, sağ çocuk 2*src+2 için 2*dst+1.

Bu, klasik yinelemeli ters çevirmedir. Düğüm nesneleriyle kuyruktan bir düğüm alıp iki çocuğunu yer değiştirir ve onları kuyruğa eklersiniz. Burada ise yer değiştirme, hedef indekse yazılarak gerçekleştirilir; çünkü dizi, iki alt ağacı tek adımda yer değiştiremez. Her gerçek düğüm, ait olduğu kesin konumla birlikte kuyruğa bir kez girer; böylece sonuçta her düğüm çıktıda yansıtılmış konumunda bulunur. İlk örnekte çiftler şu sırayla çıkar: (0, 0), (1, 2), (2, 1), (3, 6), (4, 5), (6, 3).

Zaman karmaşıklığı O(n)'dir. Kuyruk en fazla bir düzey ve biraz fazlasını tutar; en geniş düzey w için bu, O(w) olur ve buna O(n) boyutundaki çıktı eklenir. Taşabilecek bir çağrı yığını yoktur; dolayısıyla bu sürüm, derin işaretçi tabanlı ağaçlara da değişiklik yapılmadan uygulanabilir.

Algoritma

Uzunluğu tam seviyelere yuvarlayın ve bu boyutta bir çıktıyı -1 ile doldurun.
(0, 0) çiftini bir kuyruğa koyun.
Öndeki kuyruktan bir (src, dst) çifti alın ve out[dst] = tree[src] olarak ayarlayın.
Dizi içinde olan ve -1 olmayan her çocuk için (2*src+1, 2*dst+2) ve (2*src+2, 2*dst+1) çiftlerini kuyruğa ekleyin.
Kuyruk boşaldığında sondaki -1 girdilerini kaldırın ve çıktıyı döndürün.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size
    queue = [(0, 0)]  # pairs: index in tree, index of its mirrored spot in out
    head = 0
    while head < len(queue):
        src, dst = queue[head]
        head += 1
        out[dst] = tree[src]
        left, right = 2 * src + 1, 2 * src + 2
        if left < n and tree[left] != -1:
            queue.append((left, 2 * dst + 2))  # the left child goes to the right
        if right < n and tree[right] != -1:
            queue.append((right, 2 * dst + 1))  # the right child goes to the left
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Tuzaklar ve uç durumlar

Aynalanmış ağacın kendisini açıklamak kısa sürer. Hatalar diziden kaynaklanır: boyutundan, sonundan ve iki girdinin yer değiştirmesinin gerçekte neyi taşıdığından.

tree[2*i+1] ve tree[2*i+2] öğelerini yerinde değiştirmek. Bu, iki değerin yerini değiştirir ama altlarındaki alt ağaçları değiştirmez. İlk örnekte 1 ve 2 indislerini değiştirmek, 1 ve 4 değerlerini 8'in altında asılı bırakır.
Çıktıyı girdi kadar uzun yapmak. İkinci örnekteki 6 gibi, aynalanmış bir düğüm girdinin son indisinin ötesine düşebilir. Çıktıyı tam seviyeleri kapsayacak boyutta ayarlayın.
Son kırpmayı unutmak. Hem dolgulu girdilerde hem de aynalanmış ağacın girdi ağacından daha erken sona erdiği durumlarda, yanıtın sonunda -1 bulunmaz.
Tüm diziyi ters çevirmek. Bu, seviyeleri birbirine karıştırır: son yaprak kök olur.
Sınır denetimini atlamak. Dizi son düğümden hemen sonra bitebileceği için bir çocuk indisi girdinin sonunu aşabilir.
Dizilerin 1'den başladığı Lua ve R'de ofseti karıştırmak. 2*i+1 aritmetiği için indisleri 0 tabanlı tutun ve tree[i + 1] öğesini okuyun.

Sıkça sorulan sorular3

İkili bir ağacı tersine çevirmek ne anlama gelir?

İkili bir ağacı tersine çevirmek, onu ayna görüntüsüne dönüştürür: her düğümde sol ve sağ alt ağaçlar yer değiştirir. Kök yerinde kalır, en soldaki yaprak en sağdaki olur ve sola doğru uzanan bir zincir sağa doğru uzanan bir zincire dönüşür. İki kez tersine çevirmek, ağacı eski hâline getirir.

İkili bir ağacı tersine çevirmenin zaman karmaşıklığı nedir?

Her düğüm bir kez ziyaret edilir, bu nedenle zaman karmaşıklığı O(n) olur. Özyinelemeli bir çözüm, derinliği h olan bir ağaç için O(h) yığın alanı kullanır; kuyruk tabanlı bir çözüm ise en geniş seviye için O(w) alan kullanır. Bu dizi sürümünde yanıtın kendisi yeni bir dizidir ve bu da O(n) ekler.

İkili bir ağacı özyineleme kullanmadan nasıl tersine çevirirsiniz?

Bir kuyruk veya yığın kullanın. Kökten başlayın ve her düğümü dışarı aldığınızda sol ve sağ çocuklarını yer değiştirip çocukları sıraya ekleyin. Yapı onları hangi sırayla verirse versin, her düğümün yer değiştirme işlemi bir kez yapılır. Dizi biçiminde bunun yerine indeks çiftlerini kuyruğa ekler ve her düğümü doğrudan yansıma konumuna yazarsınız.

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

Test #1

Test #2

Test #3

Argüman

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

Beklenen Çıktı

[5, 8, 3, 9, -1, 4, 1]