İçeriğe geç

Yükseklik dengeli ağaç kontrolü

Kolay#post-order#early-exit~15 dk

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

Hedef zaman
O(n)
Hedef alan
O(h)

Kısıtlar

  • n ≤ 5000 nodes

Kodda değil de fikirde mi takıldın? Ağaç derinliği ve denge bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır