En sığ yaprak derinliği
Görev tanımı
Problem
İkili bir ağacın kökü verildiğinde, kökten bir yaprağa inen en kısa yoldaki düğüm sayısını döndür; yaprak çocuğu olmayan bir düğümdür. Boş bir ağacın derinliği 0. Yalnız bir çocuğu olan bir düğüm yaprak değildir, bu yüzden ondan geçen bir yol o çocuğa devam etmek zorundadır.
Örnekler
Input: tree = 6, left 2 (whose left is 1, whose left is 0), right 9
Output: 2
Neden: 9 kökün bir adım altında bir yaprak
Input: tree = 1, right 2, whose right is 3
Output: 3
Neden: 1 ve 2'nin her birinin bir çocuğu var, bu yüzden yalnız 3 bir yaprak
Input: tree = empty
Output: 0
Neden: edge case: hiç düğüm yok
İpuçları
0 / 3
En sığ yaprak herhangi bir tarafta olabilir, ama ağacı seviye seviye keşfederken karşılaştığın ilk yapraktan asla derin olamaz.
Kökten başlayarak her seferinde bir seviye keşfet, her düğümün derinliğini hatırla ve her düğümde onun bir yaprak olup olmadığını kontrol et.
Düğüm ve derinlik çiftlerinden oluşan bir kuyrukla genişlik öncelikli arama çalıştır. Çıkardığın, ne sol ne sağ çocuğu olan ilk düğüm cevabı verir; derinliğini hemen döndür. Yalnız bir çocuğu olan bir düğüm yaprak değildir.
- Hedef zaman
- O(n)
- Hedef alan
- O(w)
Kısıtlar
- the tree may be empty
Çözüm
Genişlik öncelikli arama (BFS) düğümleri derinlik sırasıyla çıkarır; bu yüzden çıkardığı ilk yaprak en sığ yapraktır ve arama orada durabilir. Bu erken durma, bir yaprak büyük bir ağacın köküne yakın durduğunda işe yarar; orada derinlik öncelikli bir dolaşma yine her düğümü ziyaret ederdi. Kolay hata, tek çocuklu bir düğümde iki alt ağaç derinliğinin küçüğünü almak: eksik taraf 0 bildirir ve düğüm yanlışlıkla yaprak sayılır. En kötü durumda zaman O(n), kuyrukta tutulan en geniş seviye için alan O(w).
from collections import deque
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def min_depth(root):
if not root:
return 0
queue = deque([(root, 1)])
while queue:
node, depth = queue.popleft()
if not node.left and not node.right:
return depth # BFS meets the shallowest leaf first
for child in (node.left, node.right):
if child:
queue.append((child, depth + 1))
print(min_depth(T(6, T(2, T(1, T(0))), T(9)))) # -> 2
print(min_depth(T(1, None, T(2, None, T(3))))) # -> 3
print(min_depth(None)) # -> 0Kodda değil de fikirde mi takıldın? Ağaç temelleri bunu anlatıyor.