En derin seviye sayısı
Görev tanımı
Problem
İkili bir ağacın kökü verildiğinde, kökten herhangi bir yaprağa inen en uzun yoldaki seviye sayısını döndür. Yalnız kökü olan bir ağaç bir seviye, boş bir ağaç sıfır seviye sayılır.
Örnekler
Input: tree = 3 with children 9 and 20, where 20 has children 15 and 7
Output: 3
Neden: 3, 20, 15 yolu üç seviyeyi kapsıyor
Input: tree = 1 with a right child 2, whose right child is 3
Output: 3
Neden: tamamen tek tarafa yatık bir ağaç da her seviyeyi sayar
Input: tree = empty
Output: 0
Neden: edge case: sayılacak seviye yok
İpuçları
0 / 3
Bir ağacın derinliği tamamen iki alt ağacı tarafından belirlenir; onlar da birer ağaçtır. Bütün çözüm bu kendine benzerlik.
Bir düğümün cevabını çocuklarının cevapları cinsinden tanımla ve eksik çocuk için aritmetiği işleten bir temel durum seç.
Olmayan bir düğüm için sıfır seviye bildir. Gerçek her düğüm için iki çocuğa da derinliklerini sor, büyük olanı al ve düğümün kendisinin kapladığı seviye için bir ekle.
- Hedef zaman
- O(n)
- Hedef alan
- O(h)
Kısıtlar
- the tree may be empty
Çözüm
Derinlik özyinelemeli olarak tanımlanır: olmayan bir düğüm sıfır seviye katar, var olan bir düğüm de iki alt ağacının derin olanından bir fazla katar. Bu tek kural, boş çocuk dışında hiçbir özel durum olmadan dengeli ve yatık ağaçları aynı şekilde ele alır. Her düğüm tam bir kez ziyaret edilir. Zaman O(n), h ağacın yüksekliği olmak üzere call stack için alan O(h).
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def depth(node):
if node is None: return 0 # an absent branch adds no level
# a node sits exactly one level above its deeper subtree
return 1 + max(depth(node.left), depth(node.right))
print(depth(T(3, T(9), T(20, T(15), T(7))))) # -> 3
print(depth(T(1, None, T(2, None, T(3))))) # -> 3
print(depth(None)) # -> 0Kodda değil de fikirde mi takıldın? Ağaç derinliği ve denge bunu anlatıyor.