Diameter of Binary Tree

+10

Seviye sırasına göre tree dizisinde saklanan bir ikili ağaç verilir. Kök 0 indeksinde bulunur, i indeksindeki düğümün çocukları 2*i+1 (sol) ve 2*i+2 (sağ) indekslerinde bulunur, boş bir yeri -1 belirtir ve dizinin sonunda fazladan -1 girdileri olabilir. Ağacın çapını döndür: Herhangi iki düğüm arasındaki en uzun yol üzerindeki kenar sayısını. Yol kökten geçebilir veya tek bir alt ağacın içinde kalabilir.

Fonksiyon

diameterOfBinaryTree(tree: integer-array) → integer

treeinteger-array: ikili ağacı seviye sırasına göre, boş konumlar için -1
Döndürürinteger: iki düğüm arasındaki en uzun yol üzerindeki kenar sayısı

Kısıtlar

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

Örnekler

Girdi: tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]
Çıktı: 4
Açıklama: 7, 4, 3, 8, 6 yolu (indeksler 9, 4, 1, 0, 2), dört kenarla birbirine bağlanan beş düğüm içerir. Kök düğümde yön değiştirir: sol taraftan aşağı üç kenar ve sağ taraftan aşağı bir kenar.

Girdi: tree = [2, 5, -1, 1, 9, -1, -1, 3, -1, -1, 4]
Çıktı: 4
Açıklama: 3, 1, 5, 9, 4 yolu dört kenara sahiptir ve 1 indeksindeki 5 noktasında yön değiştirir. Kökün sağ çocuğu yoktur, bu nedenle kökten geçen bir yol yalnızca sol tarafındaki üç kenardan oluşur.

Girdi: tree = [6, -1, -1]
Çıktı: 0
Açıklama: Tek bir düğümün kenarı yoktur. En uzun yol, uzunluğu 0 olan düğümün kendisidir.

Ek soru

Yolun kendisini, çapın bir ucundan diğer ucuna kadar düğüm değerlerini nasıl döndürürdünüz?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

En uzun yolun kökten geçmesi gerekmez; bu nedenle kökün iki tarafını ölçmek yeterli değildir. Her yolun, yukarı çıkıştan aşağı inişe döndüğü en yüksek bir düğümü vardır ve bir düğümde dönen en uzun yol, o düğümün sol yüksekliği ile sağ yüksekliğinin toplamıdır. Tek bir sondan başa geçiş, tüm yükseklikleri aşağıdan yukarıya hesaplar ve yol boyunca her dönüş noktasını O(n) sürede kontrol eder.

Her düğüm çiftini ölçün

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Önce, dizide nasıl gezinileceğine bakalım. i indeksindeki düğümün sol çocuğu 2*i+1, sağ çocuğu 2*i+2 indeksindedir; dolayısıyla ebeveyni (i-1)/2 indeksinde yer alır ve sonuç aşağı yuvarlanır. Bir konum yalnızca indeksi dizi sınırları içindeyse ve oradaki değer -1 değilse gerçektir. [8, 3, 6, 1, 4, -1, -1, -1, -1, 7] dizisinde, 9 indeksindeki 7 değerinin ebeveyni 4 indeksindedir ve bu 4 değerinin ebeveyni 1 indeksindedir.

Çap, iki düğüm arasındaki en büyük uzaklıktır; bu nedenle her çifti ölçebilirsin. a ve b indeksleri arasındaki uzaklığı bulmak için, buluşana kadar her seferinde büyük indeksten başlayarak köke doğru birer adım ilerle. Daha büyük bir indeks hiçbir zaman daha üst bir seviyede olmadığından, bu adım buluşma noktasını geçmez. Adım sayısı kenar sayısıdır. 9 ve 2 için: 9, önce 4'e, ardından 1'e çıkar; 2, 0'a çıkar ve 1, 0'a çıkar. Dört adım.

Bu doğru, ancak yavaştır. En büyük test, 16383 düğümden oluşan tam bir ağaçtır; bu da yaklaşık 1.3 × 10^8 çift oluşturur ve her çift için en fazla 26 adım gerekir. Tek bir yanıt için milyarlarca adım, süre sınırını çok aşar.

Algoritma

Tüm gerçek düğümlerin indekslerini topla.
Her (a, b) çifti için edges = 0 değerini ayarla ve a == b olana kadar tekrarla: büyük indeksi ebeveyniyle değiştir ve edges değerine 1 ekle.
Gördüğün en büyük edges değerini sakla ve döndür.

def diameterOfBinaryTree(tree):
    nodes = [i for i, value in enumerate(tree) if value != -1]
    best = 0
    for x in range(len(nodes)):
        for y in range(x + 1, len(nodes)):
            a, b = nodes[x], nodes[y]
            edges = 0
            while a != b:
                # A larger index is never higher up, so climb from it.
                if a > b:
                    a = (a - 1) // 2
                else:
                    b = (b - 1) // 2
                edges += 1
            best = max(best, edges)
    return best

Her düğümde her iki yüksekliği de ölçün

Sezgi

En uzun yola bakın: En yüksek düğümden, yani yukarı çıkmayı bırakıp aşağı inmeye başladığı düğümden başlayın. Oradan sol tarafta olabildiğince aşağı, sağ tarafta da olabildiğince aşağı gider. height(c) değerinin c düğümünden aşağı doğru inen en uzun yoldaki düğüm sayısını verdiğini, boş bir konum için 0 olduğunu varsayın. O hâlde i düğümünde dönüş yapan en uzun yolun kenar sayısı height(2*i+1) + height(2*i+2) olur; bu düğümlerin her biri için bir kenar vardır.

Bu yüzden her düğümü dönüş noktası olarak deneyin ve en iyisini saklayın. İkinci örnekte, 1 indeksindeki 5 düğümünün solunda (1, 3) yükseklik 2, sağında (9, 4) ise yükseklik 2'dir; bu da dört kenarlı bir yol oluşturur. Kökün solundaki yükseklik 3, sağındaki yükseklik ise 0'dır; bu yalnızca üç kenar verir.

Her height çağrısı bir alt ağacın tamamını dolaşır ve bir düğüm, üstündeki her ata düğüm için yeniden dolaşıldığından, işlem miktarı O(n·h)'dir. h ≤ 14 olduğunda bu, burada yeterince hızlıdır; ancak zincir biçimli bir işaretçi ağacında h, n'e ulaşabilir ve aynı fikir O(n²) maliyete yol açar. Yinelenen height çağrılarının yarattığı bu gereksiz iş yükünü son yaklaşım ortadan kaldırır.

Algoritma

height(i) fonksiyonunu yaz: Boş bir konum için 0, aksi hâlde 1 + max(height(2*i+1), height(2*i+2)).
Her gerçek düğüm i için height(2*i+1) + height(2*i+2) değerini hesapla.
Bu toplamların en büyüğünü döndür.

def diameterOfBinaryTree(tree):
    n = len(tree)

    def height(i):
        # Nodes on the longest downward path from i; an empty spot has 0.
        if i >= n or tree[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    best = 0
    for i in range(n):
        if tree[i] != -1:
            # The longest path that turns at node i goes down both sides.
            best = max(best, height(2 * i + 1) + height(2 * i + 2))
    return best

Yükseklikler üzerinde tek bir post-order geçiş

Sezgi

Bir düğümün yüksekliği yalnızca iki çocuğunun yüksekliğine bağlıdır ve bunlar dönüm noktası kontrolünün ihtiyaç duyduğu aynı iki sayıdır. Bu yüzden bunları aşağıdan yukarıya doğru bir kez hesapla. Bir post-order dolaşım, ebeveyninden önce her iki çocuğu da tamamlar. Her düğümde artık elinde left ve right vardır: yanıtı left + right ile güncelle ve 1 + max(left, right) değerini ebeveyne aktar.

İlk örnekte yaprak 7, 1 döndürür; üstündeki 4, 2 döndürür; 3 ise diğer çocuğu 1'in yüksekliği 1 olduğundan 3 döndürür. 6, 1 döndürür. Kök düğümde left + right = 3 + 1 = 4, yani yanıt elde edilir. Diğer düğümlerin sunduğu en iyi değer, 1 + 2 = 3 ile 3'tür.

Her düğüm bir kez ziyaret edilir, bu nedenle zaman karmaşıklığı O(n)'dir; özyineleme ağacın derinliği kadar derindir, O(h), yani seviye başına yaklaşık bir çağrı çerçevesi. Yanıt, özyinelemenin dışındaki bir değişkende tutulur; çünkü bir çağrının döndürdüğü şey (bir yükseklik), sonunda istediğin şey (bir yol uzunluğu) değildir.

Algoritma

best = 0 olarak ayarla ve height(i) yaz. Boş bir yer için 0 döndür.
left = height(2*i+1) ve right = height(2*i+2) değerlerini hesapla.
best değerini, best ve left + right değerlerinden büyük olanı olarak ayarla.
1 + max(left, right) döndür.
height(0) çağır ve best döndür.

def diameterOfBinaryTree(tree):
    n = len(tree)
    best = 0

    def height(i):
        # Returns the height of node i and updates best on the way back up.
        nonlocal best
        if i >= n or tree[i] == -1:
            return 0
        left = height(2 * i + 1)
        right = height(2 * i + 2)
        best = max(best, left + right)  # the longest path that turns at node i
        return 1 + max(left, right)

    height(0)
    return best

Tuzaklar ve uç durumlar

Yanlış yanıtların çoğu yanlış şeyi sayar veya yanlış düğümde ölçüm yapar.

Kenarlar yerine düğümleri saymak. 7, 4, 3, 8, 6 yolu beş düğümden oluşur ve uzunluğu 4 olur; tek bir düğümün çapı 0'dır.
Yalnızca kökten geçen yolu ölçmek. İkinci örnekte kökten geçen en iyi yol üç kenardan oluşur ve yanıt, 1 indeksinde dönüş yaparak dört olur.
Özyinelemeli çağrıdan çapı döndürmek. Daha uzun yollar oluşturmak için üst düğümün çocuklarının yüksekliklerine ihtiyacı vardır; çap ayrı bir değişkende tutulmalıdır.
İki yükseklik tanımını karıştırmak. Düğümleri sayan yüksekliklerde ve boş konum için 0 kullanıldığında left + right zaten kenar sayısıdır. Kenarları sayan yüksekliklerde boş konum için -1 ve left + right + 2 gerekir. İki tanımın yarısını kullanmak sonucu bir veya iki eksik ya da fazla verir.
Dizinin sonunu aşarak okumak. Dizinin sonuna yakın bir yaprak, son girdinin ötesinde çocuk indekslerine sahip olabilir. Dizi sonrasındaki bir indeksi boş konum olarak değerlendirin.
Dizilerin 1'den başladığı Lua ve R'deki ofseti karıştırmak. 2*i+1 aritmetiği için düğüm indekslerini 0 tabanlı tutun ve tree[i + 1] okuyun.

Sıkça sorulan sorular3

İkili Ağacın Çapı'nın zaman karmaşıklığı nedir?

Son-sıralı çözüm her düğümü bir kez ziyaret eder; bu nedenle, yineleme için O(h) ek alan kullanarak O(n) zamanda çalışır; burada h, ağacın yüksekliğidir. Yükseklikleri her düğümde ayrı ayrı hesaplamak O(n·h) maliyetlidir; zincir şeklindeki bir ağaçta bu değer O(n²) olur.

İkili bir ağacın çapı her zaman kökten geçer mi?

Hayır. En uzun yol tamamen tek bir alt ağaç içinde olabilir; örneğin kökün bir tarafında kısa bir dal, diğer tarafında ise derin ve dallı budaklı bir alt ağaç bulunduğunda. Bu nedenle yalnızca kökte değil, her düğümde left + right değerini kontrol edersin.

Çap düğümlerle mi yoksa kenarlarla mı sayılır?

Burada çap, yol üzerindeki ardışık düğümler arasındaki bağlantılar olan kenarlarla sayılır; bu nedenle tek bir düğümün çapı 0, birbirine bağlı iki düğümün çapı ise 1 olur. Bazı kitaplar bunun yerine düğümleri sayar ve sonuç bir fazla çıkar. 1 eklemeden veya çıkarmadan önce problemin hangisini istediğini kontrol et.

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

Test #1

Test #2

Test #3

Argüman

tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]

Beklenen Çıktı

Diameter of Binary Tree

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her düğüm çiftini ölçün

Her düğümde her iki yüksekliği de ölçün

Yükseklikler üzerinde tek bir post-order geçiş

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler