Lowest Common Ancestor of a BST
Kamu mendapatkan binary search tree yang disimpan dalam urutan heap di array tree: root berada pada indeks 0, anak-anak dari indeks i berada di 2*i+1 (kiri) dan 2*i+2 (kanan), dan -1 menandai posisi kosong. Setiap nilai di subtree kiri sebuah node lebih kecil daripada nilai node tersebut, dan setiap nilai di subtree kanannya lebih besar.
Tulis lowestCommonAncestor, yang mengembalikan nilai leluhur bersama terendah dari nilai p dan q, yang keduanya ada di tree: node terdalam yang memiliki keduanya di subtree-nya. Sebuah node termasuk dalam subtree-nya sendiri, jadi jika p berada di atas q, jawabannya adalah p.
Fungsi
- treeinteger-array
- pohon pencarian biner dalam urutan level, dengan -1 untuk posisi kosong
- pinteger
- nilai pertama yang dicari
- qinteger
- nilai kedua yang dicari
- Mengembalikaninteger
- nilai node terdalam yang memiliki p dan q di dalam subpohonnya
Batasan
1 ≤ tree.length ≤ 32767- Setiap
tree[i]adalah-1atau nilai dengan0 ≤ tree[i] ≤ 105. tree[0]tidak pernah-1, jadi tree memiliki setidaknya satu node.- array tersebut mungkin diakhiri dengan entri
-1tambahan setelah node terakhir. - Kedua anak dari posisi kosong juga kosong, dan kedalamannya paling banyak
14. - Pohon tersebut adalah binary search tree yang valid, jadi semua nilainya berbeda.
pdanqadalah nilai dari node dalam pohon. Keduanya dapat diberikan dalam urutan apa pun dan nilainya mungkin sama.
Contoh
- Input
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
- Output
- 8
- Penjelasan
- Dengan menelusuri ke atas dari
3dan15, node pertama yang dicapai keduanya adalah8:3adalah anak kirinya, dan15berada di bawah12di sisi kanannya. Root20juga merupakan leluhur bersama, tetapi posisinya lebih tinggi.
- Input
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
- Output
- 12
- Penjelasan
10adalah anak kiri dari12, dan sebuah simpul dianggap sebagai leluhurnya sendiri, jadi12memiliki kedua nilai tersebut dan tidak ada simpul di bawahnya yang memilikinya. Di sinipadalah nilai yang lebih besar.
- Input
- tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
- Output
- 70
- Penjelasan
- Kedua nilai lebih besar daripada root
50, jadi keduanya berada di sebelah kanannya. Di70, keduanya berpisah:55lebih kecil dan berada di sebelah kiri, di bawah60, sedangkan80lebih besar.
Pertanyaan lanjutan
Apa yang akan kamu ubah jika p atau q mungkin tidak ada di dalam pohon, dan fungsi harus mengembalikan -1 dalam kasus tersebut?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Berdirilah di root. Jika
pdanqlebih kecil daripada nilainya, di subtree mana kedua node berada?Selama kedua nilai berada di sisi yang sama dari node saat ini, setiap leluhur bersama yang lebih dalam juga berada di sisi tersebut. Node pertama tempat keduanya tidak berada di sisi yang sama, atau yang menyimpan salah satunya, adalah node yang kamu cari.
Mulai dari indeks
0. Selama kedua nilai lebih kecil daritree[i], pindah ke2*i+1; selama keduanya lebih besar, pindah ke2*i+2. Jika tidak, kembalikantree[i].
Solusi
Pohon pencarian memberi tahu kamu di setiap simpul tempat nilai berada: nilai yang lebih kecil di kiri, nilai yang lebih besar di kanan. Mulai dari akar, lalu bergerak ke sisi yang memuat kedua nilai. Simpul pertama tempat keduanya tidak lagi berbagi sisi adalah jawabannya, dan kamu mencapainya melalui satu jalur.
Cari seluruh pohon, abaikan urutannya
Intuisi
Method ini berfungsi pada pohon biner apa pun. Fungsi rekursif find(i) melaporkan isi subtree pada i. Node yang menyimpan p atau q melaporkan dirinya sendiri: jika nilai lainnya berada di bawahnya, node itu adalah jawabannya, dan jika tidak, node yang lebih tinggi akan melihat keduanya. Node lainnya meminta jawaban dari kedua anaknya. Jika keduanya melaporkan sesuatu, p dan q berada di sisi yang berbeda dan node ini adalah tempat keduanya bertemu; jika hanya satu yang melaporkan sesuatu, teruskan jawaban itu ke atas.
Untuk 3 dan 15, 8 mendapat indeks 3 dari sisi kiri dan indeks 10 dari sisi kanan, lalu melaporkan dirinya sendiri. Fungsi ini mungkin mengunjungi setiap node: waktu O(n), dan O(h) untuk rekursinya.
Algoritma
- Tulis
find(i). Jika posisi diikosong (melewati akhir atau-1), kembalikan-1. - Jika
tree[i]adalahpatauq, kembalikani. - Panggil
findpada2*i+1dan2*i+2. Jika keduanya menemukan sesuatu, kembalikani. - Jika tidak, kembalikan sisi yang menemukan sesuatu, atau
-1. - Kembalikan
tree[find(0)].
def lowestCommonAncestor(tree, p, q):
n = len(tree)
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 tree[i] == -1:
return -1
if tree[i] == p or tree[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 tree[find(0)]Bandingkan kedua jalur pencarian
Intuisi
Cari nilai dengan cara biasa: mulai dari root, pergi ke kiri jika nilainya lebih kecil daripada node dan ke kanan jika nilainya lebih besar. Jalur dari root ke sebuah node bersifat unik, jadi penelusuran melewati setiap leluhur nilai tersebut dan tidak melewati yang lain.
Catat kedua jalur. Keduanya berbagi node sampai nilainya mengambil arah yang berbeda, jadi bagian awal yang sama berisi daftar leluhur bersama, dan nilai terakhirnya adalah yang terendah. Untuk 3 dan 15, jalurnya adalah 20, 8, 3 dan 20, 8, 12, 15: keduanya berbagi 20, 8, jadi jawabannya adalah 8. Setiap penelusuran membutuhkan satu langkah per level: waktu O(h), dan ruang O(h) untuk daftar tersebut.
Algoritma
- Tulis
path(target): mulai dari indeks0, catattree[i], berhenti saat nilainya sama dengantarget, jika tidak, pindah ke2*i+1jikatargetlebih kecil dan ke2*i+2jika lebih besar. - Buat jalur ke
pdan jalur keq. - Telusuri kedua list dari awal dan kembalikan nilai terakhir yang sama.
def lowestCommonAncestor(tree, p, q):
def path(target):
# The values met on the way from the root down to target.
values = []
i = 0
while True:
values.append(tree[i])
if tree[i] == target:
return values
i = 2 * i + 1 if target < tree[i] else 2 * i + 2
to_p, to_q = path(p), path(q)
# Both paths start at the root; the answer is the last value they share.
answer = to_p[0]
for a, b in zip(to_p, to_q):
if a != b:
break
answer = a
return answerTelusuri ke bawah hingga nilainya terpisah
Intuisi
Kedua jalur searah selama p dan q bergerak dengan cara yang sama, jadi telusuri keduanya sekaligus. Pada simpul yang menyimpan v, jika kedua nilai lebih kecil, keduanya berada di subtree kiri, begitu juga setiap leluhur bersama di bawah v: bergerak ke kiri. Jika keduanya lebih besar, bergerak ke kanan.
Jika tidak, satu nilai lebih kecil dan nilai lainnya lebih besar, sehingga tidak ada anak v yang menyimpan keduanya, atau salah satunya sama dengan v, yang merupakan leluhurnya sendiri. Dengan cara apa pun, v adalah simpul terdalam di atas keduanya. Dalam contoh ketiga, 50 berada di bawah kedua nilai, jadi kamu bergerak ke kanan menuju 70, tempat 55 lebih kecil dan 80 lebih besar. Satu pasang perbandingan per tingkat menghasilkan waktu O(h) dan ruang O(1).
Algoritma
- Mulai dari indeks
i = 0. - Baca
v = tree[i]. - Jika
p < vdanq < v, pindah ke2*i+1dan ulangi. - Jika
p > vdanq > v, pindah ke2*i+2dan ulangi. - Jika tidak, kembalikan
v.
def lowestCommonAncestor(tree, p, q):
i = 0 # start at the root
while True:
value = tree[i]
if p < value and q < value:
i = 2 * i + 1 # both are smaller: the answer is on the left
elif p > value and q > value:
i = 2 * i + 2 # both are larger: the answer is on the right
else:
return value # they split here, or one of them is this node
Jebakan dan kasus tepi
- Menggunakan
≤dan≥dalam pengujian perpindahan. Denganp = 12danq = 10, penelusuran melewati12hingga10, lalu mengembalikan10atau keluar dari pohon. - Mengasumsikan
p < q. Dalam contoh kedua,padalah nilai yang lebih besar. Uji keduanya terhadap node, atau tukar posisinya terlebih dahulu. - Mengembalikan indeks, bukan nilai. Jawabannya adalah
tree[i], bukani. - Di Lua dan R, indeks array dimulai dari 1. Pertahankan indeks node berbasis 0 untuk perhitungan
2*i+1dan bacatree[i + 1].
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu untuk mencari lowestCommonAncestor di BST?
Penelusuran dari root mengikuti satu jalur, jadi membutuhkan waktu O(h) untuk pohon dengan kedalaman h dan ruang ekstra O(1). Pada pohon seimbang, kompleksitasnya O(log n); pada pohon yang berbentuk satu jalur, kompleksitasnya O(n).
Bagaimana LCA pada binary search tree berbeda dari LCA pada binary tree?
Dalam binary tree biasa, sebuah nilai bisa berada di mana saja, jadi kamu mungkin perlu mencari di setiap node, dengan usaha O(n). Dalam search tree, membandingkan kedua nilai dengan sebuah node memberi tahu kamu sisi mana yang menyimpan masing-masing nilai, jadi kamu mengikuti satu jalur dari root.
Bisakah sebuah node menjadi leluhur bersama terendah bagi dirinya sendiri?
Ya. Sebuah node dianggap sebagai leluhur dari dirinya sendiri, jadi ketika p berada di atas q, jawabannya adalah p, dan ketika kedua nilai sama, jawabannya adalah nilai tersebut.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def lowestCommonAncestor(tree, p, q):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15] p = 3 q = 15
Output yang diharapkan
8