Lowest Common Ancestor of a Binary Tree

Q: Apa perbedaannya dengan leluhur bersama terendah dalam pohon pencarian biner?

Dalam pohon pencarian, membandingkan p dan q dengan sebuah node memberi tahu kamu di sisi mana masing-masing berada, sehingga satu jalur dari akar dapat menemukan jawabannya dalam O(h). Di sini, perbandingan tidak memberi tahu apa pun, jadi kamu mencari di subtree.

Q: Bisakah kamu menemukan leluhur bersama terendah dengan pointer induk?

Ya. Dalam array ini, parent dari indeks i adalah (i-1)/2 yang dibulatkan ke bawah. Pindahkan indeks yang lebih besar di antara keduanya ke parent-nya sampai keduanya sama; indeks yang lebih besar tidak pernah menjadi ancestor dari indeks yang lebih kecil. Dengan node yang saling terhubung, masukkan ancestor dari p ke dalam set, lalu naik dari q hingga menemukan yang pertama di dalam set tersebut.

SedangTree traversal Rekursi

+10

Kamu mendapatkan pohon biner dalam array root, dengan urutan heap: akar berada pada indeks 0, anak-anak dari indeks i berada pada 2*i+1 (kiri) dan 2*i+2 (kanan), dan -1 menandakan tempat kosong. Nilainya berbeda dan tidak mengikuti urutan tertentu.

Kembalikan nilai leluhur bersama terendah dari p dan q, yaitu nilai dari dua node yang berbeda: node terdalam yang subpohonnya memuat keduanya. Subpohon mencakup node teratasnya, jadi jika q berada di bawah p, jawabannya adalah p.

Fungsi

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

rootinteger-array: pohon biner dalam urutan level, dengan -1 untuk posisi kosong
pinteger: nilai dari satu node
qinteger: nilai node lain
Mengembalikaninteger: nilai node paling bawah yang subtree-nya memuat p dan q

Batasan

2 ≤ root.length ≤ 32767
Setiap root[i] adalah -1 atau nilai dengan 0 ≤ root[i] ≤ 10⁴.
root[0] tidak pernah -1, dan pohon memiliki setidaknya dua simpul.
array tersebut mungkin diakhiri dengan entri -1 tambahan setelah node terakhir.
Kedua anak dari posisi kosong juga kosong, dan kedalamannya paling banyak 14.
Semua nilai dalam pohon berbeda, dan tidak mengikuti urutan apa pun.
p dan q adalah nilai dari dua node yang berbeda dalam tree, dalam urutan apa pun.

Contoh

Input: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 6q = 9
Output: 3
Penjelasan: 6 adalah anak kiri dari 3, dan 9 berada di bawah 4 di sebelah kanan 3, jadi keduanya bertemu di 3. Membandingkan nilai akan menunjuk ke root 8: 6 lebih kecil dan 9 lebih besar.

Input: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 4q = 7
Output: 4
Penjelasan: 7 adalah anak kiri dari 4, dan subtree dari 4 mencakup 4 itu sendiri, jadi jawabannya adalah 4.

Input: root = [1, -1, 6, -1, -1, 3, 0, -1, -1, -1, -1, -1, -1, -1, -1]p = 3q = 0
Output: 6
Penjelasan: Root 1 tidak memiliki child kiri. Child kanannya 6 memiliki 3 di sebelah kiri dan 0 di sebelah kanan, jadi nilai-nilai tersebut bertemu di 6.

Pertanyaan lanjutan

Jika p atau q mungkin tidak ada, dengan -1 sebagai jawabannya, pintasan mana dalam satu kali lintasan yang tidak berfungsi, dan bagaimana kamu tetap menyelesaikannya dalam satu traversal?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Tidak ada urutan yang memberi tahu kamu sisi mana yang menyimpan suatu nilai, jadi kamu harus melihatnya. Satu kali penelusuran post-order memungkinkan setiap subtree melaporkan temuannya, lalu nilai-nilai bertemu di node pertama yang menerima informasi dari kedua sisi.

Susuri jalan sambil mencari di setiap sisi

Intuisi

Turun dari root, lalu di setiap node cari p dan q di subtree kiri. Jika keduanya ada di sana, turun ke kiri. Jika tidak ada keduanya, turun ke kanan. Jika masing-masing ada di satu sisi, nilainya terpisah, dan node ini adalah jawabannya. Node yang menyimpan p atau q juga menjadi jawabannya, karena nilai lainnya pasti berada di bawahnya. Untuk 6 dan 9, root menemukan keduanya di sisi kirinya, dan di 3, satu-satunya 6 hanya menyimpan p.

Setiap langkah turun menelusuri seluruh subtree, sehingga h level membutuhkan biaya O(n·h), dan O(n²) pada pohon yang tinggi dan sempit tanpa batas kedalaman. Pencarian di 8 sudah mengunjungi setiap node di bawah 3, dan langkah di 3 mengunjungi beberapa node lagi.

Algoritma

Tulis contains(i, value): false untuk posisi kosong (melewati akhir atau -1), true jika root[i] sama dengan value, jika tidak, periksa kedua anak.
Mulai dari i = 0. Jika root[i] adalah p atau q, kembalikan nilainya.
Jika subtree kiri di 2*i+1 memuat kedua nilai, pindah ke sana. Jika tidak memuat keduanya, pindah ke 2*i+2.
Jika tidak, kembalikan root[i].

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

Satu penelusuran post-order

Intuisi

Biarkan setiap subtree memberikan jawaban satu kali, dari bawah ke atas. find(i) mengembalikan indeks jawaban jika subtree pada i menyimpan kedua nilai, indeks p atau q jika subtree tersebut menyimpan salah satunya, dan -1 jika subtree tersebut tidak menyimpan keduanya.

Node yang menyimpan p atau q mengembalikan indeksnya sendiri tanpa memeriksa bagian bawah. Jika nilai lainnya ada di subtree-nya, node ini adalah jawabannya; jika tidak, node yang lebih tinggi akan menerima hasil dari kedua sisi. Node lainnya memeriksa kedua anaknya. Dua hasil berarti kedua nilai berasal dari sisi yang berbeda dan bertemu di sini. Satu hasil diteruskan ke atas tanpa perubahan, baik itu salah satu nilai maupun jawaban akhir.

Pada contoh pertama, 3 menerima indeks 3 dari anak kiri dan 10 dari anak kanan, mengembalikan indeksnya sendiri, yaitu 1, lalu root meneruskannya ke atas. Setiap node dikunjungi satu kali: waktu O(n), rekursi O(h).

Algoritma

find(i) menghasilkan -1 untuk indeks yang melewati akhir atau nilai -1.
Node yang nilainya p atau q menghasilkan i tanpa memeriksa bagian di bawahnya.
Node lainnya menghitung left = find(2*i+1) dan right = find(2*i+2). Jika keduanya bukan -1, node tersebut menghasilkan i; jika tidak, hasilnya adalah yang bukan -1, atau -1.
Kembalikan root[find(0)].

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)]

Jebakan dan kasus tepi

Membandingkan nilai dengan node. Pohon tidak berurutan: pada contoh pertama, penelusuran itu berhenti di root 8, bukan di 3.
Meneruskan true atau false alih-alih indeks. Parent tidak dapat mengetahui apakah jawaban akhir sudah berada di bawahnya.
Membaca child tanpa memeriksa panjangnya. 9 pada indeks 10 memiliki indeks child 21 dan 22, yang berada setelah entri terakhir.
Mengembalikan find(0), sebuah indeks, alih-alih root[find(0)].
Di Lua dan R, array dimulai dari 1: tetap gunakan indeks node berbasis 0 dan baca root[i + 1].

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu leluhur bersama terendah pada pohon biner?

Penelusuran post-order memasuki setiap node paling banyak satu kali: waktu O(n). Stack rekursi menyimpan satu frame untuk setiap tingkat, sehingga penggunaan ruangnya O(log n) pada tree yang seimbang dan O(n) pada tree yang berbentuk seperti jalur.

Apa perbedaannya dengan leluhur bersama terendah dalam pohon pencarian biner?

Dalam pohon pencarian, membandingkan p dan q dengan sebuah node memberi tahu kamu di sisi mana masing-masing berada, sehingga satu jalur dari akar dapat menemukan jawabannya dalam O(h). Di sini, perbandingan tidak memberi tahu apa pun, jadi kamu mencari di subtree.

Bisakah kamu menemukan leluhur bersama terendah dengan pointer induk?

Ya. Dalam array ini, parent dari indeks i adalah (i-1)/2 yang dibulatkan ke bawah. Pindahkan indeks yang lebih besar di antara keduanya ke parent-nya sampai keduanya sama; indeks yang lebih besar tidak pernah menjadi ancestor dari indeks yang lebih kecil. Dengan node yang saling terhubung, masukkan ancestor dari p ke dalam set, lalu naik dari q hingga menemukan yang pertama di dalam set tersebut.

def lowestCommonAncestor(root, p, q):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan