Binary Tree Right Side View

Q: İkili Ağacın Sağdan Görünümü algoritmasının zaman ve alan karmaşıklığı nedir?

Zaman, n düğüm için O(n) olur ve hiçbir çözüm düğümleri atlayamaz; çünkü bir seviyenin en sağdaki düğümü herhangi bir yerde bulunabilir. Kuyruk için alan karmaşıklığı O(w) olup burada w en geniş seviyedir; h seviyeli bir ağaçta sağdan öncelikli gezinme içinse O(h) olur.

OrtaAğaç dolaşma Kuyruk

+10

root dizisi bir ikili ağacı 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 sonda fazladan -1 girdileri bulunabilir.

Ağaca sağ tarafından bak. Her seviye sana tam olarak bir düğüm gösterir: en sağdakini; diğerlerini ise gizler. Bu değerleri kökün bulunduğu seviyeden en derin seviyeye kadar sırala.

Fonksiyon

rightSideView(root: integer-array) → integer-array

rootinteger-array: yığın sırasındaki ağaç, boş bir konum için -1 ile
Döndürürinteger-array: her düzeyin en sağdaki değeri, önce en üst düzey

Kısıtlar

1 ≤ root.length ≤ 32767
Her root[i], -1 ya da 0 ≤ root[i] ≤ 10⁴ koşulunu sağlayan bir değerdir.
Düğüm değerleri birbirinden farklıdır.
root[0] asla -1 olmaz, bu nedenle ağacın en az bir düğümü vardır.
Dizi, son düğümün ardından fazladan -1 girdileriyle sona erebilir.
Boş bir noktanın her iki çocuğu da boştur ve ağacın en fazla 14 seviyesi vardır.

Örnekler

Girdi: root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
Çıktı: [5, 9, 1, 3]
Açıklama: Sağdan 5, 9 ve 1 (indeks 6) görürsünüz. Dördüncü seviyede yalnızca sol alt ağaçta 7'nin altında, 8. indekste bulunan 3 yer alır. Sağ tarafta bu derinliğe ulaşan başka bir şey olmadığı için 3 görünür.

Girdi: root = [6, 0, -1, 8, -1, -1, -1]
Çıktı: [6, 0, 8]
Açıklama: Ağaç, sol çocuklardan oluşan bir zincirdir: 6, 0, 8. Her seviyede bir düğüm bulunur, bu yüzden üçünü de görürsün; ancak hiçbiri sağ çocuk değildir.

Girdi: root = [42]
Çıktı: [42]
Açıklama: Uzunluğu 1 olan bir dizi: kök 42 öğesinin hiç çocuk yuvası yoktur ve görünüm bu tek değerden oluşur.

Ek soru

Her düğümün soldan sağa sıralı bir liste olarak tutulan herhangi bir sayıda çocuğa sahip olabildiği bir ağacın sağdan görünümünü nasıl elde edersin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Her düzeyin en sağdaki düğümünü görürsünüz ve bunun sağ çocuk olması gerekmez: 1. örneğin son değeri sol alt ağaçta yer alır. Genişlik öncelikli arama, bu düğümü her turun son düğümü yapar; önce sağa giden derinlik öncelikli bir dolaşım ise o düzeydeki diğer düğümlerden önce bu düğüme ulaşır.

Önce genişlik, her seviyenin son düğümü

Sezgi

Ağacı her turda bir seviye işle. Bir tur başladığında kuyrukta soldan sağa tam olarak tek bir seviye bulunur; bu nedenle turda kuyruktan çıkardığın son indeks, o seviyenin en sağındaki düğümdür ve değeri yanıta eklenir.

1. örnekte turlar [5], [2, 9], [7, 4, 1] ve [3] şeklindedir ve son elemanları 5, 9, 1, 3 değerlerini verir. Belirleyici olan taraf değil, seviyedir: 3 sol alt ağaçta bulunur, ancak kendi seviyesinde tektir.

Her indeks kuyruğa bir kez eklenip kuyruktan bir kez çıkarılır, bu nedenle zaman karmaşıklığı O(n)'dir. Kuyruk, en geniş seviyeye kadar büyür; en kötü durumda O(n) olur.

Algoritma

Kökün 0 indeksini kuyruğa ekle.
Kuyruğun uzunluğunu s olarak kaydederek bir tura başla.
s indeks çıkar. Her i indeksi için, dizinin uzunluğundan küçük ve -1 olmayan 2i+1 indeksini kuyruğa ekle, ardından aynı koşulları sağlıyorsa 2i+2 indeksini ekle.
Turda kuyruktan çıkarılan son indeksin değerini ekle.
Kuyruk boşalana kadar tekrarla, ardından yanıtı döndür.

from collections import deque


def rightSideView(root):
    n = len(root)
    view = []
    queue = deque([0])  # node indexes; the root is never empty
    while queue:
        size = len(queue)  # exactly the nodes of the current level
        for j in range(size):
            i = queue.popleft()
            if j == size - 1:
                view.append(root[i])  # the last node of this level
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and root[child] != -1:
                    queue.append(child)
    return view

Derinlik öncelikli, önce sağ çocuk

Sezgi

Önce sağ çocuğu, sonra sol çocuğu deneyerek derinlik öncelikli dolaşın ve kökte 0 olan derinlik bilgisini taşıyın. Dolaşma ilk kez d derinliğine ulaştığında, cevapta tam olarak d değer bulunur. O anda düğümün değerini ekleyin ve o seviyedeki sonraki tüm düğümleri yok sayın.

Bu ilk düğüm en sağdakidir: Bir seviyeye giden iki yolun ayrıldığı her yerde dolaşma, geri dönüp sol kola geçmeden önce sağ kolu en alta kadar izler. 1. örnekte dolaşma 5, 9, 1, 2, 4, 7, 3 düğümlerini ziyaret eder: derinliklerinde zaten bir değer bulunan 2, 4 ve 7 düğümlerini atlar ve 3 değerini ekler.

Her düğüm bir kez ziyaret edilir; süre O(n)'dir ve yığında seviye başına bir çağrı bulunur; en fazla 14 çağrı.

Algoritma

Boş bir yanıtla ve derinliği 0 olan kökle başlayın.
Dizinin sonunu geçmiş veya -1 değerini taşıyan bir indeksi atlayın.
Yanıtın uzunluğu derinliğe eşit olduğunda değeri ekleyin: yürüyüş yeni bir seviyeye ulaşmıştır ve bu seviyeye sağdan ulaşmıştır.
Önce sağ çocuğa 2i+2, ardından sol çocuğa 2i+1 özyinelemeli olarak ilerleyin; her seferinde bir seviye daha derine inin.
Yanıtı döndürün.

def rightSideView(root):
    n = len(root)
    view = []

    def visit(i, depth):
        if i >= n or root[i] == -1:
            return
        if depth == len(view):  # the first node met on this level
            view.append(root[i])
        # Right before left, so the rightmost node of every level comes first.
        visit(2 * i + 2, depth + 1)
        visit(2 * i + 1, depth + 1)

    visit(0, 0)
    return view

Tuzaklar ve uç durumlar

Kökten başlayarak yalnızca sağ çocukları izlemek. Örnek 1 bu durumda [5, 9, 1] sonucunu verir ve 3 değerini atlar; örnek 2 ise [6] sonucunu verir.
Her seviyenin son yuvasını okumak: root[2^(d+1)-2]. Örnek 2'de 6 indeksinde -1 bulunur; görünür düğüm, 3 indeksindeki 8 değeridir.
Bir çocuk yuvasındaki uzunluk kontrolünü atlamak. Örnek 1'de 3 son girdidir, dolayısıyla 17 ve 18 çocuk yuvaları mevcut değildir.
Her turdaki son düğümü tutarken önce sağ çocuğu kuyruğa eklemek. Bu, sol görünümü toplar: [5, 2, 7, 3].
Sağdan önce yürüyüşte sonraki düğümlerin önceki düğümlerin üzerine yazmasına izin vermek; bu da sol görünümü verir.

Sıkça sorulan sorular3

İkili Ağacın Sağdan Görünümü algoritmasının zaman ve alan karmaşıklığı nedir?

Zaman, n düğüm için O(n) olur ve hiçbir çözüm düğümleri atlayamaz; çünkü bir seviyenin en sağdaki düğümü herhangi bir yerde bulunabilir. Kuyruk için alan karmaşıklığı O(w) olup burada w en geniş seviyedir; h seviyeli bir ağaçta sağdan öncelikli gezinme içinse O(h) olur.

Soldan öncelikli bir derinlik öncelikli arama bunu çözebilir mi?

Evet, ilk değeri korumak yerine üzerine yazarsan. Soldan önce ilerleyen bir dolaşım, her seviyedeki düğümlerle soldan sağa karşılaşır; bu nedenle her düğümün değerini derinliğinde sakla ve sonraki düğümlerin önceki değerlerin üzerine yazmasına izin ver. Her derinlikte en sağdaki değer kalır. Bu hâlâ O(n) karmaşıklığındadır, ancak düğüm başına bir kez yazma yapar.

Burada genişlik öncelikli arama mı, derinlik öncelikli arama mı kullanmalıyım?

İkisi de doğrusaldır. Genişlik öncelikli arama tanıma uyar; her turda bir seviye ilerler. Derinlik öncelikli arama yalnızca geçerli yolu tutar; bu da geniş bir ağaçta bellek tasarrufu sağlar ve özyinelemeli biçimi birkaç satır daha kısadır.

def rightSideView(root):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

root = [5, 2, 9, 7, 4, -1, 1, -1, 3]

Beklenen Çıktı

[5, 9, 1, 3]