Maximum Depth of Binary Tree
Seviye sırasına göre tree dizisinde saklanan bir ikili ağaç alırsınız. 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 konumu belirtir ve dizinin sonunda fazladan -1 girdileri olabilir. Ağacın maksimum derinliğini döndürün: kökten bir yaprağa giden en uzun yoldaki düğüm sayısı.
Fonksiyon
- treeinteger-array
- ikili ağacı seviye sırasına göre, boş bir konum için -1 kullanarak
- 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],-1veya0 ≤ tree[i] ≤ 1000koşulunu sağlayan bir değerdir. tree[0]hiçbir zaman-1değildir, dolayısıyla ağaçta en az bir düğüm vardır.- Dizi, son düğümden sonra fazladan
-1girdileriyle bitebilir. - Boş bir noktanın her iki çocuğu da boştur ve derinlik en fazla
14olur.
Ö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,9indeksleri) olup 4 düğümden oluşur.1üzerinden geçen yol 2 düğümden sonra sona erer.
- Girdi
- tree = [7, -1, -1]
- Çıktı
- 1
- Açıklama
- İki
-1girdisi, kökün boş çocuk konumlarıdır. Kök tek başına bir düğümlük bir yoldur; bu nedenle derinlik0değil,1'dir.
- Girdi
- tree = [2, -1, 9, -1, -1, -1, 4]
- Çıktı
- 3
- Açıklama
- Kök
2'nin sol çocuğu yoktur.2indeksindeki sağ çocuğu9'un, sağ çocuğu olarak6indeksindeki4vardır; bu, 3 düğümlü bir yoldur.
Ek soru
En uzun kökten yaprağa giden yol üzerindeki değerleri ve bu yolun uzunluğunu nasıl döndürürdünüz? Birden fazla yol eşit uzunluktaysa hangisini döndürürdünüz?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Kökü düşün. Sol alt ağacının derinliğini ve sağ alt ağacının derinliğini bilseydin, tüm ağacın derinliği ne olurdu?
Kök için
1artı iki alt ağacın derinliklerinden büyük olanıdır; boş bir konumun derinliği0olur. Aynı kural her düğüm için geçerlidir; bu nedenle her düğümün ne kadar derinde olduğunu bilen bir dolaşma yanıtı bulabilir.Bir çift yığını tut; her çift bir düğüm indeksi ve derinliğinden oluşsun, kök düğüm 1 derinliğinde başlasın. Bir çifti yığından çıkar, görülen en büyük derinliği kaydet ve dizinin içinde bulunan ve
-1olmayan her çocuğu, derinliği bir artırarak2*i+1ve2*i+2konumlarında yığına ekle.
Çözüm
Derinlik en uzun dala göre belirlenir ve her düğümü ziyaret etmeden hangi dalın en uzun olduğunu bilemezsin. Bu yüzden her düğümde ne kadar derinde olduğunu bilen tek bir tam dolaşım gerekir. Özyineleme, düzeylere göre genişlik öncelikli arama ve kendi yığınını kullanan derinlik öncelikli arama bunu tek geçişte yapar.
İki alt ağaçta özyineleme
Sezgi
Bir çocuk konumu, dizinin sınırları içindeyse ve değeri -1 değilse geçerlidir. Bir düğümden geçen en derin yol, daha derindeki alt ağaca iner; dolayısıyla i indeksindeki derinlik, düğümün kendisi için 1 ile 2*i+1 ve 2*i+2 indekslerindeki derinliklerden büyük olanının toplamıdır. Boş bir konumun derinliği 0'dır; bu da özyinelemeyi sona erdirir. Bir yaprak 1 + max(0, 0) = 1 değerini alır ve değerler köke doğru yükselir.
Her düğüm bir kez ziyaret edilir. Çağrı yığını, geçerli yolun her seviyesi için bir çerçeve tutar: O(h); burada en fazla 14'tür.
Algoritma
depth(i)fonksiyonunu yaz:idizinin sonunu geçmişse veyatree[i]-1ise0döndür.- Aksi hâlde
1 + max(depth(2*i+1), depth(2*i+2))döndür. depth(0)döndür.
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, seviye sayısıdır; bu nedenle yolları izlemek yerine seviyeleri sayabilirsiniz. Bir kuyruk, düğümleri seviye sırasına göre ziyaret eder. Her gruptan önce kuyruğun boyutunu okuyun: bu düğümler tam olarak bir seviyeye aittir, çünkü grup sırasında eklediğiniz çocuk düğümler kuyruğa bunların arkasından girer. Her grup derinliğe 1 ekler. İlk örnekte gruplar [5], [8, 1], [3] ve [6] olduğundan yanıt 4'tür.
Kuyruk aynı anda bir seviyeyi tutar; en geniş seviye için O(w) alan gerekir. Derinliği 14 olan tam bir ağaçta bu, 16383 düğümün 8192'sidir.
Algoritma
- Kök dizin olan
0'ı kuyruğa ekle vedepth = 0olarak ayarla. - Kuyruk boş değilken
depthdeğerini1artır ve kuyruğun boyutunu oku. - Bu kadar dizini kuyruktan çıkar. Her biri için, dizinin içinde bulunan ve
-1olmayan2*i+1ve2*i+2çocuk dizinlerini kuyruğa ekle. - Kuyruk boşaldığında
depthdeğ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 depthDerinlik öncelikli arama, açıkça belirtilmiş bir yığın kullanarak
Sezgi
Her düğümün ne kadar derinde olduğunu başka hiçbir şey hatırlamadığı için, çiftlerden oluşan kendi yığınını, bir düğüm indeksini ve derinliğini tut. Kökün derinliği 1 olacak şekilde (0, 1) ile başla. Her düğüm, ona ulaşan yolun uzunluğunu taşıyarak yığına bir kez eklenir; bu nedenle çıkardığın en büyük derinlik cevaptır. İlk örnekte 6, (9, 4) olarak yığına eklenir.
Yığın, her seviye için yaklaşık bir bekleyen kardeş düğüm tutar: O(h); taşacak bir çağrı yığını yoktur. Aynı kod, herhangi bir derinlikteki işaretçi tabanlı bir ağaçta da çalışır.
Algoritma
(0, 1)öğesini bir yığına ekle vebest = 0olarak ayarla.(i, depth)çiftini yığından çıkar vebestdeğerinibestiledepthdeğerlerinden büyük olanı olarak ayarla.- Dizi içinde bulunan ve
-1olmayan her2*i+1ve2*i+2çocuk indeksi için, onudepth + 1ile birlikte yığına ekle. - Yığın boşalana kadar tekrarla, ardından
bestdeğ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
- Düğümler yerine kenarları saymak.
[7, -1, -1]derinliği1olan bir ağaçtır,0değil. - Sınır kontrolünü atlamak. İlk örnekte, 9. indeksteki
6düğümünün çocuk indeksleri 19 ve 20'dir; bunlar dizinin sonunu aşar.tree[child]değerini okumadan öncechild < nkontrolünü yap. - Derinliği dizinin uzunluğundan hesaplamak. Sondaki
-1girdileri, düğüm olmayan bir seviyeye ulaşır:[7, -1, -1]uzunluğu 3 olan ama derinliği 1 olan bir dizidir. - Toplu döngü içinde kuyruğun boyutunu okumak. Toplu işlem sırasında eklenen çocuklar bu boyutu değiştirir, bu yüzden önce kaydet.
- Dizilerin 1'den başladığı Lua ve R'de ofseti karıştırmak.
2*i+1için düğüm indekslerini 0 tabanlı tut vetree[i + 1]değerini oku.
Sıkça sorulan sorular3
İ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) olur. Derinlik öncelikli sürümler, geçerli yol için O(h) ek alan kullanır; burada h derinliktir. Genişlik öncelikli sürüm ise en geniş seviye için O(w) alan kullanır; bu, tam bir ağaçtaki düğümlerin yaklaşık yarısıdır.
İkili ağacın maksimum derinliğini bulmak için DFS mi yoksa BFS mi kullanmalısınız?
Her ikisi de O(n) zamanda çalışır. Derinlik öncelikli aramayı yazmak daha kısadır ve derinlikle orantılı bellek kullanır; bu da geniş ve sığ ağaçlar için uygundur. Genişlik öncelikli arama seviyeleri doğrudan sayar ve en geniş seviyenin boyutuyla orantılı bellek kullanır; bu da derin ve dar ağaçlar için uygundur. Minimum derinlik için BFS kazanır, çünkü ilk yaprakta durabilir.
İ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ı; yüksekliği ise ondan en derin yaprağına kadar olan adım sayısını ifade eder. Ağacın maksimum derinliği, kökün yüksekliğine eşittir. Bu problem düğümleri sayar; bu nedenle tek bir düğümün derinliği 1'dir; kenarları saymak bir eksik sonuç verir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def maxDepth(tree):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Beklenen Çıktı
4