Boundary Traversal of Binary Tree
Array root menyimpan binary tree dalam urutan level: root berada di indeks 0, anak dari indeks i berada di 2i+1 (kiri) dan 2i+2 (kanan), -1 menandakan posisi kosong, dan mungkin ada entri -1 tambahan di bagian akhir. Leaf adalah node tanpa anak.
Kembalikan batasnya berlawanan arah jarum jam dari root:
- Root.
- Batas kiri, dari atas ke bawah: mulai dari anak kiri root, pindah ke anak kiri jika ada, jika tidak, pindah ke anak kanan. Berhenti sebelum leaf.
- Semua leaf, dari kiri ke kanan.
- Batas kanan, dari bawah ke atas: kebalikan dari batas kiri, mulai dari anak kanan root.
Tidak ada node yang dicantumkan dua kali, jadi tree dengan satu node hanya menghasilkan root-nya.
Fungsi
- rootinteger-array
- pohon biner secara berurutan berdasarkan level, dengan -1 untuk posisi kosong
- Mengembalikaninteger-array
- nilai-nilai batas, berlawanan arah jarum jam dari akar
Batasan
1 ≤ root.length ≤ 32767- Setiap
root[i]adalah-1atau nilai dengan0 ≤ root[i] ≤ 105. root[0]tidak pernah-1, jadi pohon memiliki setidaknya satu node.- array bisa diakhiri dengan entri
-1tambahan setelah node terakhir. - Kedua anak dari posisi kosong juga kosong, dan kedalamannya paling banyak
14. - Nilai node berbeda-beda.
Contoh
- Input
- root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
- Output
- [7, 3, 1, 4, 6, 8, 9]
- Penjelasan
- Setelah akar
7, batas kiri adalah3: anaknya1adalah daun. Daunnya adalah1,4,6,8. Batas kanan adalah9, di atas daun8.
- Input
- root = [10, 4, -1, -1, 6, -1, -1, -1, -1, 5, 8]
- Output
- [10, 4, 6, 5, 8]
- Penjelasan
4tidak memiliki anak kiri, jadi batas kiri beralih ke6, lalu berhenti di daun5. Daun5,8menyusul. Akar tidak memiliki anak kanan.
- Input
- root = [3]
- Output
- [3]
- Penjelasan
- Root adalah seluruh pohon. Root dicantumkan satu kali, bukan dicantumkan lagi sebagai leaf.
Pertanyaan lanjutan
Bagaimana kamu akan menyusun batas searah jarum jam: akar, tepi kanan dari atas ke bawah, daun dari kanan ke kiri, lalu tepi kiri dari bawah ke atas?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Bagilah jawaban menjadi empat bagian: akar, sisi kiri, daun, sisi kanan. Bagian mana yang merupakan satu jalur turun melewati pohon, dan bagian mana yang memerlukan penelusuran penuh?
Setiap sisi adalah satu jalur: dari anak root, terus bergerak ke anak di sisi itu, atau ke anak yang lain jika sisi tersebut kosong. Daun dalam urutan dari kiri ke kanan berasal dari penelusuran depth-first yang mengunjungi subtree kiri terlebih dahulu. Perhatikan titik pertemuannya: daun tempat sisi berakhir termasuk dalam kumpulan daun.
Turun dari indeks
1dan tambahkan setiap simpul non-daun. Lalu tambahkan setiap simpul daun dengan penelusuran pre-order. Setelah itu, turun dari indeks2, kumpulkan setiap simpul non-daun, lalu tambahkan daftar tersebut dalam urutan terbalik.
Solusi
Jawaban menggabungkan empat bagian: akar, jalur menuruni tepi kiri, daun dari kiri ke kanan, dan jalur menuruni tepi kanan yang dibaca dari belakang. Pada titik pertemuan, daun yang mengakhiri sebuah tepi dan akar yang merupakan daun harus masing-masing dicantumkan satu kali.
Telusuri ketiga bagian secara terpisah
Intuisi
Setiap edge adalah satu jalur: dari anak root, daftarkan node hingga node berikutnya adalah leaf, yang dicantumkan oleh bagian leaf. Penelusuran pre-order yang bergerak ke kiri sebelum ke kanan menemukan leaf dalam urutan dari kiri ke kanan, karena setiap node di subtree kiri berada di sebelah kiri subtree kanan, berapa pun kedalamannya. Kumpulkan edge kanan dari atas ke bawah, lalu tambahkan dalam urutan terbalik.
Setiap edge mengikuti satu jalur dan penelusuran leaf mengunjungi setiap node satu kali: waktu O(n), dengan rekursi sedalam h level.
Algoritma
- Mulai dari root; jika node tersebut adalah leaf, kembalikan node itu.
- Dari indeks
1, selama node ada dan bukan leaf, tambahkan node itu lalu pindah ke child kirinya, atau ke child kanannya jika tidak ada child kiri. - Telusuri secara pre-order, mulai dari kiri, dari indeks
1dan2, lalu tambahkan setiap leaf. - Dari indeks
2, lakukan hal yang sama seperti langkah 2 dengan mengutamakan child kanan, lalu kumpulkan node-node tersebut. - Tambahkan node yang terkumpul dalam urutan terbalik.
def boundaryTraversal(root):
n = len(root)
def real(i):
return i < n and root[i] != -1
def is_leaf(i):
return not real(2 * i + 1) and not real(2 * i + 2)
result = [root[0]]
if is_leaf(0):
return result
# 1. The left boundary, top-down, stopping before its leaf.
i = 1
while real(i) and not is_leaf(i):
result.append(root[i])
i = 2 * i + 1 if real(2 * i + 1) else 2 * i + 2
# 2. Every leaf: a pre-order walk meets them from left to right.
def add_leaves(i):
if not real(i):
return
if is_leaf(i):
result.append(root[i])
return
add_leaves(2 * i + 1)
add_leaves(2 * i + 2)
add_leaves(1)
add_leaves(2)
# 3. The right boundary, collected top-down and added bottom-up.
right = []
i = 2
while real(i) and not is_leaf(i):
right.append(root[i])
i = 2 * i + 2 if real(2 * i + 2) else 2 * i + 1
result.extend(reversed(right))
return resultSatu lintasan pre-order dengan penanda sisi
Intuisi
Gabungkan penelusuran menjadi satu lintasan pre-order menggunakan stack dengan memberi setiap node sebuah flag: 1 di tepi kiri, 2 di tepi kanan, 0 di bagian dalam. Anak-anak root dimulai dengan 1 dan 2. Node tepi meneruskan flag-nya kepada anak di sisinya, atau kepada satu-satunya anaknya; setiap anak lainnya mendapat 0. Pada contoh kedua, 1 diteruskan dari 4 ke 6 lalu ke 5.
Saat node keluar dari stack, tambahkan setiap leaf dan setiap node non-leaf yang diberi flag 1; kumpulkan node non-leaf yang diberi flag 2, lalu tambahkan secara terbalik di akhir. Penelusuran pre-order mencapai setiap node tepi kiri sebelum leaf mana pun, karena tepi berbelok ke kanan hanya saat tidak ada apa pun di sebelah kirinya.
Algoritma
- Mulai dari root. Push child kanannya dengan flag
2, lalu child kirinya dengan flag1. - Pop sebuah node. Tambahkan node tersebut jika berupa leaf atau memiliki flag
1; tambahkan node non-leaf dengan flag2ke list kanan. - Push child kanannya, lalu child kirinya, masing-masing dengan flag yang diberikan oleh aturan.
- Saat stack kosong, tambahkan list kanan dalam urutan terbalik.
def boundaryTraversal(root):
n = len(root)
def real(i):
return i < n and root[i] != -1
result = [root[0]]
right = [] # the right boundary, top-down; it goes on the end reversed
# Each entry is (index, edge): 1 = left boundary, 2 = right boundary, 0 = inside.
stack = []
if real(2):
stack.append((2, 2))
if real(1):
stack.append((1, 1))
while stack:
i, edge = stack.pop()
has_left, has_right = real(2 * i + 1), real(2 * i + 2)
if not has_left and not has_right:
result.append(root[i]) # a leaf; pre-order meets them left to right
elif edge == 1:
result.append(root[i]) # the left boundary, top-down
elif edge == 2:
right.append(root[i])
# An edge passes to the child on its own side, or to an only child.
# The right child goes on the stack first, so the left one comes out first.
if has_right:
stack.append((2 * i + 2, edge if edge == 2 or not has_left else 0))
if has_left:
stack.append((2 * i + 1, edge if edge == 1 or not has_right else 0))
result.extend(reversed(right))
return result
Jebakan dan kasus tepi
- Mencantumkan sebuah node dua kali. Penelusuran edge yang tidak berhenti sebelum leaf mencantumkan
1dua kali pada contoh 1, dan tree dengan satu node tidak boleh mencantumkan root-nya lagi sebagai leaf. - Menganggap node pertama di setiap level sebagai batas kiri. Jika anak kiri root adalah leaf dan subtree kanan lebih dalam, level yang lebih dalam dimulai dengan node dari subtree kanan, tetapi batas kirinya kosong.
- Hanya mengikuti anak kiri. Pada contoh 2, batasnya harus bergerak dari
4ke anak kanannya,6. - Mengumpulkan leaf per level. Contoh 1 kemudian menghasilkan
1,8,4,6. - Di Lua dan R, pertahankan indeks node berbasis 0 untuk aritmetika
2i+1dan bacaroot[i + 1].
Pertanyaan yang sering diajukan3
Apa itu penelusuran batas pada pohon biner?
Ini mencantumkan garis besar pohon berlawanan arah jarum jam: akar, sisi kiri dari atas ke bawah, daun dari kiri ke kanan, dan sisi kanan dari bawah ke atas. Sisi-sisi tersebut tidak mencakup daunnya, sehingga tidak ada simpul yang muncul dua kali.
Apa kompleksitas waktu dari penelusuran batas?
O(n). Kedua penelusuran tepi mengikuti satu jalur masing-masing, dan penelusuran daun mengunjungi setiap node satu kali. Ruang tambahan adalah O(h) untuk rekursi atau stack.
Apakah batas kiri selalu mengikuti anak kiri?
Tidak. Jalurnya bergerak ke anak kiri jika ada, dan ke anak kanan jika tidak ada: jalur paling luar yang kamu lihat dari sebelah kiri. Jika root tidak memiliki anak kiri, batas kiri kosong.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def boundaryTraversal(root):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
Output yang diharapkan
[7, 3, 1, 4, 6, 8, 9]