Yükseklik dengeli ağaç kontrolü
Görev tanımı
Problem
Bir arama indeksi anahtarlarını ikili bir ağaçta tutuyor ve ağaç her yana yattığında onu yeniden kuruyor. Bir ağaç, her düğümde sol ve sağ alt ağaçların yükseklikleri en fazla 1 farklıysa yükseklik dengelidir. İkili bir ağacın kökü verildiğinde, yükseklik dengeliyse True döndür. Ağaçta en fazla 5.000 düğüm var, bu yüzden yüksekliği her düğümden yeniden hesaplamak israf.
Örnekler
Input: tree = 3, left 9, right 20 (children 15 and 7)
Output: True
Input: tree = 1, left 2 (left child 3 with children 4 and 4, right child 3), right 2
Output: False
Neden: kökte sol taraf 3 seviye, sağ taraf yalnız 1 seviye derin
Input: tree = empty
Output: True
Neden: edge case: boş bir ağaçta dengesiz bir şey yok
İpuçları
0 / 3
Her düğümden bir yükseklik fonksiyonu çağırmak alt düğümleri tekrar tekrar ziyaret eder; bu da uzun bir ağaçta karesel.
Bir düğüm kendini test etmek için zaten çocuklarının yüksekliklerine ihtiyaç duyar ve kendi yüksekliği onların büyüğünün bir fazlasıdır. Aşağıdan yukarı tek bir dolaşma ikisini de hesaplayabilir.
Bir postorder dolaşmadan her alt ağacın yüksekliğini döndür; ya da aşağıdaki bir alt ağacın zaten dengesiz olduğunun sinyali olarak -1 döndür. -1'i gördüğün anda doğrudan yukarı geçir.
- Hedef zaman
- O(n)
- Hedef alan
- O(h)
Kısıtlar
- n ≤ 5000 nodes
Çözüm
Tek bir postorder dolaşma her alt ağacın yüksekliğini ebeveynine döndürür; böylece her düğüm kendi dengesini çocuklarının zaten hesapladığı sayılardan kontrol edebilir. Bir düğüm iki yüksekliğinin birden fazla farklı olduğunu bulduğunda bir yükseklik yerine -1 döndürür ve her ata o -1'i daha fazla iş yapmadan doğrudan yukarı geçirir. Ağaç tam olarak kök -1 döndürmediğinde dengelidir. Her düğüm bir kez ziyaret edilir; zaman O(n), özyineleme (recursion) 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 is_balanced(root):
def height(node): # height, or -1 if unbalanced below
if node is None:
return 0
lh = height(node.left)
if lh == -1:
return -1
rh = height(node.right)
if rh == -1 or abs(lh - rh) > 1:
return -1
return 1 + max(lh, rh)
return height(root) != -1
print(is_balanced(T(3, T(9), T(20, T(15), T(7))))) # -> True
print(is_balanced(T(1, T(2, T(3, T(4), T(4)), T(3)), T(2)))) # -> False
print(is_balanced(None)) # -> TrueKodda değil de fikirde mi takıldın? Ağaç derinliği ve denge bunu anlatıyor.