İçeriğe geç

BST'de en yakın anahtar

Kolay#bst#search-path~15 dk

Görev tanımı

Problem

Bir ikili arama ağacı (BST) birbirinden farklı tam sayı anahtarlar saklıyor. Kökü ve kesirli kısmı olabilen bir hedef verildiğinde, hedefe en yakın anahtarı döndür. İki anahtar eşit yakınlıktaysa küçük olanı döndür. Ağaçta her zaman en az bir düğüm var.

Örnekler

Input:  tree = 8, left 3 with children 1 and 6 (6 has children 4 and 7),
        right 10 with a right child 14; target = 5
Output: 4
Neden: 4 ve 6 ikisi de bir uzakta, 4 daha küçük
Input:  same tree; target = 12.2
Output: 14
Neden: 14'ün uzaklığı 1,8, 10'unki ise 2,2
Input:  tree = a single node 7; target = -100
Output: 7
Neden: edge case: tek anahtar en yakın olandır

İpuçları

0 / 3

Hedef zaman
O(h)
Hedef alan
O(1)

Kısıtlar

  • keys are distinct integers
  • the tree has at least one node
  • the target may have a fractional part

Kodda değil de fikirde mi takıldın? BST'de ekleme ve arama bunu anlatıyor.

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