Maximum Depth of Binary Tree

Q: İkili Ağacın Maksimum Derinliğinin zaman karmaşıklığı nedir?

Her yaklaşım her düğümü bir kez ziyaret eder, bu nedenle zaman karmaşıklığı O(n) 'dir. Derinlik öncelikli sürümler, keşfedilen yol için O(h) ek alan kullanır; burada h derinliktir. Genişlik öncelikli sürüm, en geniş seviye için O(w) alan kullanır; bu, tam bir ağaçta düğümlerin yaklaşık yarısı olabilir.

Q: İkili ağacın maksimum derinliğini bulmak için DFS mi yoksa BFS mi kullanmalısınız?

İkisi de O(n) sürede doğru yanıtı verir. Derinlik öncelikli aramanın yazımı daha kısadır ve derinlikle orantılı bellek kullanır; bu nedenle geniş ve sığ ağaçlar için uygundur. Genişlik öncelikli arama seviyeleri doğrudan sayar ve en geniş seviyedeki düğüm sayısıyla orantılı bellek kullanır; bu nedenle derin ve dar ağaçlar için uygundur. Minimum derinliği bulmak için BFS avantajlıdır, çünkü karşılaştığı ilk yaprakta durabilir.

Q: İkili bir ağacın maksimum derinliğini özyineleme kullanmadan nasıl bulursunuz?

Bir düğüm ve derinliğinden oluşan çiftler için açık bir yığın kullanın. Kökü derinlik 1 ile başlatın, bir çifti yığından çıkarın, derinliğini kaydedin ve her çocuğu derinliğinin bir fazlasıyla yığına ekleyin. Yığından çıkardığınız en büyük derinlik cevaptır. Her seviye birer birer işlenen bir kuyruk da işe yarar; her seviye için bir artırın.

Q: İkili ağacın derinliği ile yüksekliği arasındaki fark nedir?

Bir düğümün derinliği, kökten ona kadar olan adım sayısını; bir düğümün yüksekliği ise ondan en derin yaprağa kadar olan adım sayısını ifade eder. Ağacın maksimum derinliği ile kökün yüksekliği aynı sayıdır. Bu problem düğümleri sayar, bu nedenle tek bir düğümün derinliği 1 olur; bazı kitaplar bunun yerine kenarları sayar ve bu da bir eksik verir.

KolayAğaç dolaşma

+10

Seviye sırasına göre tree dizisinde saklanan bir ikili ağaç veriliyor. 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 dizinin sonunda fazladan -1 girdileri bulunabilir. Ağacın maksimum derinliğini döndürün: kökten bir yaprağa giden en uzun yoldaki düğüm sayısı.

Fonksiyon

maxDepth(tree: integer-array) → integer

treeinteger-array: ikili ağaç, seviye sırasına göre; boş konumlar için -1
Döndürürinteger: en uzun kökten yaprağa yol üzerindeki düğüm sayısı

Kısıtlar

1 ≤ tree.length ≤ 32767
Her tree[i], -1 veya 0 ≤ tree[i] ≤ 1000 koşulunu sağlayan bir değerdir.
tree[0] hiçbir zaman -1 değildir, bu nedenle ağacın 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, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Çıktı: 4
Açıklama: En uzun yol 5, 8, 3, 6 (0, 1, 4, 9 indeksleri) olup 4 düğüm içerir. 1 üzerinden geçen yol 2 düğümden sonra sona erer.

Girdi: tree = [7, -1, -1]
Çıktı: 1
Açıklama: İki -1 girdisi, kökün boş çocuk konumlarıdır. Kök tek başına bir düğümden oluşan bir yoldur, bu nedenle derinlik 1'dir, 0 değil.

Girdi: tree = [2, -1, 9, -1, -1, -1, 4]
Çıktı: 3
Açıklama: Kök 2'nin sol çocuğu yoktur. 2 indeksindeki sağ çocuğu 9'un sağ çocuğu, 6 indeksindeki 4'tür; 3 düğümlü bir yol.

Gönderirken +13 gizli test

Ek soru

Kökten yaprağa en uzun yoldaki değerleri, yalnızca uzunluğunu değil, nasıl döndürürdünüz? Birkaç yol eşit uzunluktaysa hangisini döndürürdünüz ve bunu sözleşmede nasıl belirtirdiniz?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Derinlik, tek başına en uzun dal tarafından belirlenir ve her düğüme bakmadan hangi dalın bu olduğunu anlayamazsın. Bu nedenle görev, her düğümde ne kadar derinde olduğunu bilen tam bir dolaşımdır. Özyineleme, seviye seviye genişlik öncelikli arama ve kendi yığınını kullanan derinlik öncelikli arama bunu tek geçişte yapar; bulundukları yeri takip etme biçimleri farklıdır.

İki alt ağaç üzerinde özyineleme

Sezgi

Önce dizide nasıl gezinileceğine bakalım. i dizinindeki düğümün sol çocuğu 2*i+1, sağ çocuğu ise 2*i+2 dizinindedir. Bir çocuk, yalnızca dizini dizi sınırları içindeyse ve o konumdaki değer -1 değilse gerçektir. [5, 8, 1, -1, 3, -1, -1, -1, -1, 6] dizisinde kök 5, 1 ve 2 dizinlerinde çocuklara sahiptir; 1 dizinindeki 8'in 3 dizininde boş bir sol konumu ve sağında 4 dizininde 3 vardır; bu 3'ün de altında, 9 dizininde 6 bulunur.

Şimdi fikre bakalım. Bir düğümden geçen en derin yol, iki alt ağacından hangisi daha derinse onun içine doğru ilerler. Dolayısıyla i dizinindeki alt ağacın derinliği, düğümün kendisi için 1 artı 2*i+1 ve 2*i+2 dizinlerindeki derinliklerden büyük olanıdır. Boş bir konumun derinliği 0'dır; bu da özyinelemeyi sonlandırır. Bir yaprak 1 + max(0, 0) = 1 değerini alır ve değerler köke doğru geri yükselir.

Her düğüm bir kez ziyaret edilir, bu nedenle zaman karmaşıklığı O(n)'dir. Çağrı yığını, geçerli yoldaki her seviye için bir çerçeve tutar; h derinlik olmak üzere bu O(h)'dir ve burada en fazla 14'tür. Bu sınır, özyinelemeyi bu problemde güvenli kılar. Uzun bir zincir şeklindeki işaretçi tabanlı bir ağaçta aynı kod, Python'da 1000 çerçeve olan özyineleme sınırına takılırdı.

Algoritma

depth(i) fonksiyonunu yazın: i dizinin sonunu geçmişse veya tree[i] değeri -1 ise 0 döndürün.
Aksi takdirde 1 + max(depth(2*i+1), depth(2*i+2)) döndürün.
depth(0) döndürün.

def maxDepth(tree):
    def depth(i):
        # An index past the end or a -1 is an empty spot: depth 0.
        if i >= len(tree) or tree[i] == -1:
            return 0
        return 1 + max(depth(2 * i + 1), depth(2 * i + 2))

    return depth(0)

Genişlik öncelikli arama, seviye seviye

Sezgi

Maksimum derinlik, ağaçtaki seviye sayısıdır; bu nedenle yolları takip etmek yerine seviyeleri sayabilirsiniz. Bir kuyruk, düğümleri seviye sırasına göre ziyaret eder: kuyruğu kökle başlatın ve her düğümü kuyruktan çıkardığınızda, gerçek çocuklarını kuyruğun sonuna ekleyin.

Seviyeleri saymak için kuyruğu gruplar hâlinde işleyin. Her gruptan önce kuyruğun kaç düğüm içerdiğine bakın. Bunlar tam olarak bir seviyenin düğümleridir; çünkü grup sırasında eklediğiniz çocuklar bu düğümlerin arkasına gelir. Bu kadar düğümü çıkarın, çocuklarını kuyruğa ekleyin ve derinliğe 1 ekleyin. Kuyruk boşaldığında derinlik, grup sayısıdır. İlk örnekte gruplar [5], [8, 1], [3] ve [6] olduğundan yanıt 4 olur.

Her düğüm kuyruğa bir kez girer ve kuyruktan bir kez çıkar; zaman karmaşıklığı O(n) olur. Kuyruk, bir seferde tek bir seviyeyi tutar; en geniş seviye w için alan karmaşıklığı O(w) olur. Tam bir ağaçta en alt seviye, 14 derinliğinde toplam 16383 düğümün yaklaşık yarısı olan 8192 düğümü içerir.

Algoritma

Kök dizini 0 kuyruğa koy ve depth = 0 olarak ayarla.
Kuyruk boş olmadığı sürece depth değerini 1 artır ve kuyruğun boyutunu oku.
Bu sayıda dizini kuyruktan çıkar. Her biri için, dizi içinde olan ve -1 olmayan çocuk dizinlerini 2*i+1 ve 2*i+2 kuyruğa ekle.
Kuyruk boşaldığında depth değerini döndür.

from collections import deque


def maxDepth(tree):
    n = len(tree)
    queue = deque([0])
    depth = 0
    while queue:
        depth += 1
        for _ in range(len(queue)):  # exactly the nodes of this level
            i = queue.popleft()
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    queue.append(child)
    return depth

Belirgin bir yığın kullanarak derinlik öncelikli arama

Sezgi

Özyinelemenin yaptığı gibi yolları takip edebilirsin; bunun için tek bir özyinelemeli çağrı bile yapman gerekmez. Kendi yığınını tut ve her düğümü derinliğiyle birlikte sakla; çünkü başka hiçbir şey onun ne kadar aşağıda olduğunu hatırlamaz. (0, 1) çiftiyle başla: kök, derinliği 1.

Bir çifti çıkar, derinliğini şimdiye kadar görülen en iyi değerle karşılaştır ve her gerçek çocuğu depth + 1 ile yığına ekle. Ağaçtaki her düğüm, ona ulaşan yolun uzunluğunu taşıyarak tam bir kez yığına eklenir; dolayısıyla çıkardığın en büyük derinlik yanıttır. İlk örnekte, 9 indeksindeki 6, (9, 4) olarak eklenir ve hiçbir çift daha derine inmez.

Zaman karmaşıklığı O(n)’dir. Yığın, geçerli yol boyunca bekleyen kardeş düğümleri tutar; her seviye için en fazla yaklaşık bir tane olduğundan alan karmaşıklığı O(h)’dir. Bu, özyinelemeyle aynıdır ancak taşabilecek bir çağrı yığını kullanmaz. Bir ağaç derin olabilecekse bu sürümü tercih et; ayrıca bu yaklaşım işaretçi tabanlı ağaçlara da değişmeden uygulanabilir.

Algoritma

(0, 1) değerini bir yığına ekle ve best = 0 olarak ayarla.
(i, depth) çiftini yığından çıkar ve best değerini best ile depth değerlerinden büyük olanına ayarla.
Dizi içinde bulunan ve -1 olmayan her 2*i+1 ve 2*i+2 çocuk indeksi için, onu depth + 1 ile birlikte yığına ekle.
Yığın boşalana kadar tekrarla, ardından best değerini döndür.

def maxDepth(tree):
    n = len(tree)
    best = 0
    stack = [(0, 1)]  # (node index, depth of that node); the root is never empty
    while stack:
        i, depth = stack.pop()
        best = max(best, depth)
        for child in (2 * i + 1, 2 * i + 2):
            if child < n and tree[child] != -1:
                stack.append((child, depth + 1))
    return best

Tuzaklar ve uç durumlar

Bu problemdeki yanlış yanıtların çoğu, bir eksik sayımından veya boş bir yeri düğüm olarak değerlendirmekten kaynaklanır.

Düğümler yerine kenarları saymak. Burada tek bir düğümün derinliği 1 olur; bunun için 0 döndürmek ya da 4 düğümlü bir yol için 3 döndürmek bir eksik saymaktır.
Sınır kontrolünü atlamak. Dizinin sonuna yakın bir yaprak, son düğümden hemen sonra bitebileceği için dizideki son indisi aşan çocuk indislerine sahip olabilir. tree[child] değerini okumadan önce child < n kontrolünü yapın.
Derinliği dizinin uzunluğundan çıkarmak. Dizinin sonunda fazladan -1 girdileri olabilir; bu nedenle uzunluğu, gerçek düğümlerin bulunduğu en derin seviyeden daha derin bir seviyeye karşılık gelebilir.
-1 değerini bir değer olarak değerlendirmek. Bu, eksik bir düğümü belirtir; bu nedenle yığına eklenmemeli, kuyruğa alınmamalı veya sayılmamalıdır.
Ağacın dengeli olduğunu varsaymak. Yanıt, her sağ konumun boş olduğu 14 düğümlü sol zincirde olduğu gibi, en uzun dalı izler.
Genişlik öncelikli sürümde, döngünün içinde kuyruk boyutunu okumak. Çocuklar eklendikçe boyut değişir; bu yüzden toplu işlem başlamadan önce boyutu kaydedin.
Dizilerin 1'den başladığı Lua ve R'de ofseti karıştırmak. 2*i+1 hesabı için düğüm indislerini 0 tabanlı tutun ve tree[i + 1] değerini okuyun.

Sıkça sorulan sorular4

İkili Ağacın Maksimum Derinliğinin zaman karmaşıklığı nedir?

Her yaklaşım her düğümü bir kez ziyaret eder, bu nedenle zaman karmaşıklığı O(n)'dir. Derinlik öncelikli sürümler, keşfedilen yol için O(h) ek alan kullanır; burada h derinliktir. Genişlik öncelikli sürüm, en geniş seviye için O(w) alan kullanır; bu, tam bir ağaçta düğümlerin yaklaşık yarısı olabilir.

İkili ağacın maksimum derinliğini bulmak için DFS mi yoksa BFS mi kullanmalısınız?

İkisi de O(n) sürede doğru yanıtı verir. Derinlik öncelikli aramanın yazımı daha kısadır ve derinlikle orantılı bellek kullanır; bu nedenle geniş ve sığ ağaçlar için uygundur. Genişlik öncelikli arama seviyeleri doğrudan sayar ve en geniş seviyedeki düğüm sayısıyla orantılı bellek kullanır; bu nedenle derin ve dar ağaçlar için uygundur. Minimum derinliği bulmak için BFS avantajlıdır, çünkü karşılaştığı ilk yaprakta durabilir.

İkili bir ağacın maksimum derinliğini özyineleme kullanmadan nasıl bulursunuz?

Bir düğüm ve derinliğinden oluşan çiftler için açık bir yığın kullanın. Kökü derinlik 1 ile başlatın, bir çifti yığından çıkarın, derinliğini kaydedin ve her çocuğu derinliğinin bir fazlasıyla yığına ekleyin. Yığından çıkardığınız en büyük derinlik cevaptır. Her seviye birer birer işlenen bir kuyruk da işe yarar; her seviye için bir artırın.

İkili ağacın derinliği ile yüksekliği arasındaki fark nedir?

Bir düğümün derinliği, kökten ona kadar olan adım sayısını; bir düğümün yüksekliği ise ondan en derin yaprağa kadar olan adım sayısını ifade eder. Ağacın maksimum derinliği ile kökün yüksekliği aynı sayıdır. Bu problem düğümleri sayar, bu nedenle tek bir düğümün derinliği 1 olur; bazı kitaplar bunun yerine kenarları sayar ve bu da bir eksik verir.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]

Beklenen

Maximum Depth of Binary Tree

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

İki alt ağaç üzerinde özyineleme

Genişlik öncelikli arama, seviye seviye

Belirgin bir yığın kullanarak derinlik öncelikli arama

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler