Lowest Common Ancestor of a Binary Tree

Q: Bu, ikili arama ağacındaki en düşük ortak atadan nasıl farklıdır?

Bir arama ağacında, p ile q 'yu bir düğümle karşılaştırmak hangisinin hangi tarafta olduğunu gösterir; böylece kökten başlayan tek bir yol, yanıtı O(h) sürede bulur. Burada ise karşılaştırma hiçbir şey söylemez, bu yüzden alt ağaçları ararsınız.

Q: Ebeveyn işaretçileriyle en düşük ortak atayı bulabilir misin?

Evet. Bu dizide i indeksinin ebeveyni, aşağı yuvarlanmış (i-1)/2 değeridir. İki indeksten büyük olanı, indeksler eşit olana kadar ebeveynine taşı; büyük bir indeks, küçük bir indeksin hiçbir zaman atası değildir. Bağlı düğümlerde, p öğesinin atalarını bir kümeye ekle ve q öğesinden başlayarak kümedeki ilk düğüme ulaşana kadar yukarı çık.

OrtaAğaç dolaşma Özyineleme

+10

Yığın sıralamasındaki bir dizide root ikili ağacını alırsınız: kök 0 indeksinde, i indeksindeki düğümün çocukları 2*i+1 (sol) ve 2*i+2 (sağ) indekslerinde, boş konumlar ise -1 değerindedir. Değerler birbirinden farklıdır ve belirli bir sıralamaya uymaz.

İki farklı düğümün değerleri olan p ve q için en düşük ortak atanın değerini döndürün: her ikisini de alt ağacında barındıran en derin düğüm. Bir alt ağaç tepe düğümünü de içerir; bu nedenle q, p'nin altındaysa yanıt p'dir.

Fonksiyon

lowestCommonAncestor(root: integer-array, p: integer, q: integer) → integer

rootinteger-array: ikili ağacı seviye sırasına göre, boş bir yer için -1
pinteger: bir düğümün değeri
qinteger: başka bir düğümün değeri
Döndürürinteger: Alt ağacında hem p'yi hem de q'yu barındıran en alttaki düğümün değeri

Kısıtlar

2 ≤ root.length ≤ 32767
Her root[i], -1 ya da 0 ≤ root[i] ≤ 10⁴ aralığında bir değerdir.
root[0] hiçbir zaman -1 değildir ve ağaçta en az iki düğüm vardır.
Dizi, son düğümden sonra fazladan -1 girdileriyle bitebilir.
Boş bir konumun her iki çocuğu da boştur ve derinlik en fazla 14'tür.
Ağaçtaki tüm değerler birbirinden farklıdır ve herhangi bir sıralamaya tabi değildir.
p ve q, ağaçtaki iki farklı düğümün değerleridir; sıra önemli değildir.

Örnekler

Girdi: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 6q = 9
Çıktı: 3
Açıklama: 6, 3'ün sol çocuğudur ve 9, 3'ün sağında 4'ün altında yer alır; bu nedenle 3'te buluşurlar. Değerleri karşılaştırmak kökü, yani 8'i işaret eder: 6 daha küçüktür, 9 ise daha büyüktür.

Girdi: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 4q = 7
Çıktı: 4
Açıklama: 7, 4'ün sol çocuğudur ve 4'ün alt ağacı 4'ün kendisini de içerir; bu nedenle cevap 4'tür.

Girdi: root = [1, -1, 6, -1, -1, 3, 0, -1, -1, -1, -1, -1, -1, -1, -1]p = 3q = 0
Çıktı: 6
Açıklama: Kök 1'in sol çocuğu yoktur. Sağ çocuğu 6'nın solunda 3, sağında ise 0 bulunur; bu nedenle değerler 6'da birleşir.

Ek soru

Yanıtın -1 olabileceği, yani p veya q'nun bulunmayabileceği durumda, tek geçişteki hangi kestirme bozulur ve yine de tek bir dolaşımda nasıl tamamlarsın?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Hiçbir sıralama, bir değerin hangi tarafta olduğunu söylemez; bu yüzden bakman gerekir. Tek bir son sıralı geçiş, her alt ağacın bulduğunu bildirmesini sağlar ve değerler, iki taraftan da haber alan ilk düğümde buluşur.

Her iki tarafı da arayarak aşağı in

Sezgi

Kökten aşağı ilerle ve her düğümde sol alt ağaçta p ve q değerlerini ara. İkisi de oradaysa sola git. Hiçbiri yoksa sağa git. Biri varsa diğeri yoksa değerler farklı dallardadır ve bu düğüm yanıttır. p veya q değerini tutan bir düğüm de yanıttır; çünkü diğer değer onun altında bulunmalıdır. 6 ve 9 için kök ikisini de solunda bulur ve 3 düğümünde yalnızca p değerini tutan tek 6 bulunur.

Aşağı inerken her adımda bir alt ağacın tamamı arandığından, h seviye O(n·h) maliyet getirir; derinlik sınırı olmayan, uzun ve dar bir ağaçta maliyet O(n²) olur. 8 düğümündeki arama, 3 düğümünün altındaki her düğümü zaten ziyaret etmiştir ve 3 düğümündeki adımda bazıları yeniden ziyaret edilir.

Algoritma

contains(i, value) yazın: Boş bir konum için (sonrasındaysa veya -1 ise) false, root[i] değeri value'ya eşitse true, aksi hâlde her iki çocuğu da sorgulayın.
i = 0 noktasından başlayın. root[i], p veya q ise onu döndürün.
2*i+1 konumundaki sol alt ağaç her iki değeri de içeriyorsa oraya ilerleyin. İkisini de içermiyorsa 2*i+2 konumuna ilerleyin.
Aksi hâlde root[i] değerini döndürün.

def lowestCommonAncestor(root, p, q):
    n = len(root)

    def contains(i, value):
        # Is value somewhere in the subtree at index i?
        if i >= n or root[i] == -1:
            return False
        if root[i] == value:
            return True
        return contains(2 * i + 1, value) or contains(2 * i + 2, value)

    i = 0  # p and q are always inside the subtree at i
    while True:
        if root[i] == p or root[i] == q:
            return root[i]  # one value is here, the other is below it
        left = 2 * i + 1
        p_left = contains(left, p)
        q_left = contains(left, q)
        if p_left and q_left:
            i = left  # both on the left
        elif not p_left and not q_left:
            i = 2 * i + 2  # both on the right
        else:
            return root[i]  # one on each side

Tek bir post-order geçişi

Sezgi

Her alt ağacın aşağıdan yukarıya doğru bir kez yanıt vermesini sağlayın. find(i), i konumundaki alt ağaç her iki değeri de içeriyorsa yanıtın indeksini, değerlerden birini içeriyorsa p veya q değerinin indeksini, ikisini de içermiyorsa -1 değerini döndürür.

p veya q değerini içeren bir düğüm, altına bakmadan kendi indeksini döndürür. Diğer değer alt ağacındaysa bu düğüm yanıttır; değilse daha yukarıdaki bir düğüm her iki taraftan da bilgi alır. Diğer tüm düğümler iki çocuğa da sorar. İki sonuç, değerlerin farklı taraflardan gelip burada buluştuğu anlamına gelir. Tek bir sonuç, değerlerden biri de tamamlanmış yanıt da olsa, değiştirilmeden yukarı iletilir.

İlk örnekte, 3 soldan 3 indeksini, sağdan 10 değerini alır, kendi indeksi olan 1 değerini döndürür ve kök bunu yukarı iletir. Her düğüm bir kez ziyaret edilir: O(n) zaman, O(h) özyineleme.

Algoritma

find(i), dizinin sonunu aşan bir indeks veya bir -1 için -1 döndürür.
Değeri p veya q olan bir düğüm, alt düğümlere bakmadan i döndürür.
Diğer tüm düğümler left = find(2*i+1) ve right = find(2*i+2) hesaplar. İkisi de -1 değilse i döndürür; aksi takdirde -1 olmayanı veya -1 döndürür.
root[find(0)] değerini döndür.

def lowestCommonAncestor(root, p, q):
    n = len(root)

    def find(i):
        # In the subtree at index i: the index of the answer if both values are
        # inside, the index of the one that is, or -1 when neither is.
        if i >= n or root[i] == -1:
            return -1
        if root[i] == p or root[i] == q:
            return i
        left = find(2 * i + 1)
        right = find(2 * i + 2)
        if left != -1 and right != -1:
            return i  # one value on each side: this node is the answer
        return left if left != -1 else right

    return root[find(0)]

Tuzaklar ve uç durumlar

Değerleri düğümle karşılaştırmak. Ağacın sırası yoktur: ilk örnekte bu gezinme, 3 yerine kök olan 8'de durur.
Bir indeks yerine true veya false döndürmek. Ebeveyn, aranan yanıtın zaten kendi altında olup olmadığını anlayamaz.
Uzunluğu kontrol etmeden bir çocuğu okumak. 10 indeksindeki 9'un 21 ve 22 çocuk indeksleri son girdinin ötesindedir.
Bir indeks olan find(0)'ı, root[find(0)] yerine döndürmek.
Lua ve R'de diziler 1'den başlar: düğüm indekslerini 0 tabanlı tutun ve root[i + 1] okuyun.

Sıkça sorulan sorular3

İkili ağacın en düşük ortak atasının zaman karmaşıklığı nedir?

Sıralama sonrası geçiş her düğüme en fazla bir kez girer: O(n) zaman. Özyineleme yığını her seviye için bir çerçeve tutar; bu nedenle dengeli bir ağaçta alan O(log n), yol şeklindeki bir ağaçta ise O(n) olur.

Bu, ikili arama ağacındaki en düşük ortak atadan nasıl farklıdır?

Bir arama ağacında, p ile q'yu bir düğümle karşılaştırmak hangisinin hangi tarafta olduğunu gösterir; böylece kökten başlayan tek bir yol, yanıtı O(h) sürede bulur. Burada ise karşılaştırma hiçbir şey söylemez, bu yüzden alt ağaçları ararsınız.

Ebeveyn işaretçileriyle en düşük ortak atayı bulabilir misin?

Evet. Bu dizide i indeksinin ebeveyni, aşağı yuvarlanmış (i-1)/2 değeridir. İki indeksten büyük olanı, indeksler eşit olana kadar ebeveynine taşı; büyük bir indeks, küçük bir indeksin hiçbir zaman atası değildir. Bağlı düğümlerde, p öğesinin atalarını bir kümeye ekle ve q öğesinden başlayarak kümedeki ilk düğüme ulaşana kadar yukarı çık.

def lowestCommonAncestor(root, p, q):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]
p = 6
q = 9

Beklenen Çıktı