Kelas TreeNode dan BFS Mengikut Aras
Bina pepohon binari daripada tatasusunan, laksanakan BFS dengan deque untuk mencetak mengikut aras dan selesaikan kedalaman maksimum menggunakan BFS.
Kelas TreeNode dan BFS Mengikut Aras ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 1 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Asas Kelas TreeNode
Pepohon binari ialah struktur data hierarki yang setiap nodnya mempunyai paling banyak dua anak, yang dipanggil kiri dan kanan. Dalam Python, kita memodelkan nod dengan kelas mudah: class TreeNode: def __init__(self, val=0, left=None, right=None). Setiap masalah pepohon dalam temu duga bermula dengan definisi ini — anda akan melihatnya dalam kod rangka hampir setiap masalah pepohon LeetCode.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build a small tree manually:
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(root.val, root.left.val, root.right.val)Membina Pepohon daripada Tatasusunan
Masalah temu duga sering memberikan pepohon yang diwakili sebagai tatasusunan mengikut aras, dengan None menandakan nod yang tiada. Diberikan indeks i, anak kiri berada pada 2i+1 dan anak kanan pada 2i+2. Menulis fungsi pembantu untuk menyahserialkan tatasusunan ini menjadi TreeNodes yang dipautkan ialah utiliti berharga yang menjimatkan masa semasa sesi latihan.
from collections import deque
def build_tree(arr):
if not arr or arr[0] is None:
return None
root = TreeNode(arr[0])
q = deque([root])
i = 1
while q and i < len(arr):
node = q.popleft()
if i < len(arr) and arr[i] is not None:
node.left = TreeNode(arr[i])
q.append(node.left)
i += 1
if i < len(arr) and arr[i] is not None:
node.right = TreeNode(arr[i])
q.append(node.right)
i += 1
return root
root = build_tree([1, 2, 3, 4, 5, None, 6])
print(root.val, root.left.val, root.right.val)Apakah BFS dan Mengapa Baris Gilir?
Carian Lebar-Dahulu (BFS) melawati semua nod pada kedalaman d sebelum melawati mana-mana nod pada kedalaman d+1. Pelintasan aras demi aras ini ialah tepat seperti yang diberikan oleh baris gilir (FIFO): kita memasukkan akar ke dalam baris gilir, kemudian memproses nod satu demi satu sambil memasukkan anak setiap nod. Python collections.deque memberikan appendleft dan popleft O(1), menjadikannya pilihan yang tepat berbanding senarai biasa.
from collections import deque
def bfs_print(root):
if not root:
return
q = deque([root])
while q:
node = q.popleft()
print(node.val, end=' ')
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
bfs_print(root) # 1 2 3 4BFS Mengikut Aras: Mengumpulkan Mengikut Aras
Varian BFS standard mengumpulkan nod mengikut aras dengan merekodkan saiz baris gilir pada permulaan setiap lelaran. Proses tepat sebanyak nod itu, kumpulkan nilainya, kemudian beralih ke aras seterusnya. Hasilnya ialah senarai senarai — format hasil yang sangat biasa dalam temu duga untuk masalah seperti pelintasan pepohon binari mengikut aras, pelintasan zigzag dan pandangan sisi kanan.
from collections import deque
def level_order(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
level = []
for _ in range(level_size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(level_order(root)) # [[1], [2, 3], [4]]Kedalaman Maksimum melalui BFS
Kedalaman maksimum pepohon binari sama dengan bilangan aras dalam pelintasan BFSnya. Cuma kira berapa kali anda melengkapkan gelung aras. Ini memberikan penyelesaian dengan masa O(n) dan ruang O(w), dengan w ialah lebar maksimum pepohon. Untuk pepohon seimbang, w ialah O(n/2), jadi ruang kes terburuk ialah O(n).
from collections import deque
def max_depth_bfs(root):
if not root:
return 0
depth = 0
q = deque([root])
while q:
depth += 1
for _ in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return depth
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(max_depth_bfs(root)) # 3Pandangan Sisi Kanan Pepohon Binari
Pandangan sisi kanan mengembalikan nod terakhir yang kelihatan apabila anda melihat pepohon dari kanan — iaitu elemen terakhir bagi setiap aras dalam pelintasan BFS. Ini ialah penggunaan langsung BFS mengikut aras: kumpulkan nod terakhir dalam setiap gelung aras. Kerumitan masa ialah O(n), manakala ruang ialah O(w) untuk baris gilir.
from collections import deque
def right_side_view(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
for i in range(level_size):
node = q.popleft()
if i == level_size - 1:
result.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
print(right_side_view(root)) # [1, 3, 5]Lintasan Mengikut Aras Berselang-seli
Dalam lintasan berselang-seli, aras ganjil dikumpulkan dari kiri ke kanan dan aras genap dari kanan ke kiri. Pelaksanaan yang paling kemas mengekalkan baris gilir BFS tanpa perubahan dan hanya membalikkan senarai aras secara berselang-seli sebelum menambahkannya pada hasil. Jejaki arah menggunakan bendera boolean yang bertukar pada setiap aras. Cara ini mengelakkan kerumitan baris gilir hujung berganda dalam gelung dalaman.
from collections import deque
def zigzag_level_order(root):
if not root:
return []
result = []
q = deque([root])
left_to_right = True
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level if left_to_right else level[::-1])
left_to_right = not left_to_right
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(zigzag_level_order(root))Analisis Kerumitan Ruang BFS
BFS menggunakan ruang O(w) dengan w ialah lebar maksimum pepohon. Bagi pepohon binari sempurna dengan n nod, aras terakhir mempunyai (n+1)/2 nod — jadi BFS boleh menyimpan sehingga n/2 nod dalam baris gilir pada masa yang sama. Oleh itu, BFS menggunakan lebih banyak ruang berbanding DFS (O(h)) untuk pepohon seimbang yang lebar, tetapi menggunakan kurang ruang untuk pepohon senget dan dalam, apabila kedalaman timbunan panggilan DFS menyamai n.
# Space comparison: BFS vs DFS on a complete binary tree
# n=15 nodes, height=4
# BFS max queue size = 8 (last level)
# DFS max call stack = 4 (height)
# For a skewed tree (like a linked list):
# n=1000 nodes
# BFS max queue size = 1 (always 1 node per level)
# DFS max call stack = 1000 (recursion depth -> stack overflow!)
from collections import deque
def skewed_tree(n):
root = TreeNode(1)
cur = root
for i in range(2, n+1):
cur.right = TreeNode(i)
cur = cur.right
return root
root = skewed_tree(10)
print('BFS on skewed tree is safe')Purata Aras dalam Pepohon Binari
Mengira nilai purata pada setiap aras ialah satu lagi penggunaan BFS secara langsung. Jumlahkan semua nilai pada sesuatu aras, bahagikan dengan bilangannya, kemudian tambahkan hasilnya pada senarai hasil. Soalan ini menguji keupayaan anda melakukan pengiraan dalam gelung aras. Sentiasa gunakan pembahagian float dalam Python 3, iaitu pengendali /, dan kendalikan kes pinggir pepohon kosong pada permulaan.
from collections import deque
def average_of_levels(root):
if not root:
return []
result = []
q = deque([root])
while q:
size = len(q)
total = 0
for _ in range(size):
node = q.popleft()
total += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(total / size)
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(average_of_levels(root)) # [3.0, 14.5, 11.0]Kedalaman Minimum melalui BFS
Kedalaman minimum ialah jarak dari akar ke nod daun terdekat, iaitu nod tanpa anak. BFS mencari kedalaman ini secara optimum: nod daun pertama yang ditemui semasa lintasan mengikut aras pasti berada pada kedalaman minimum. Pulangkan kedalaman semasa sebaik sahaja anda menemui nod daun. Kerumitan kes terburuknya ialah O(n), tetapi proses ini sering tamat lebih awal untuk pepohon seimbang.
from collections import deque
def min_depth(root):
if not root:
return 0
q = deque([(root, 1)])
while q:
node, depth = q.popleft()
# A leaf has no children
if not node.left and not node.right:
return depth
if node.left:
q.append((node.left, depth + 1))
if node.right:
q.append((node.right, depth + 1))
return 0
root = TreeNode(2)
root.left = TreeNode(3)
root.left.left = TreeNode(4)
root.right = TreeNode(5) # leaf at depth 2
print(min_depth(root)) # 2Menghubungkan Nod Sebelah Mengikut Aras
Masalah mengisi penuding ke kanan seterusnya meminta anda menghubungkan setiap nod dengan jiran kanannya pada aras yang sama. Dengan BFS, perkara ini mudah dilakukan: dalam gelung setiap aras, tetapkan node.next = q[0] untuk semua nod kecuali nod terakhir. Ini ialah contoh klasik apabila BFS menjadikan penyelesaian jelas, manakala DFS memerlukan penjejakan penuding yang teliti merentasi subpepohon.
from collections import deque
class Node:
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
def connect(root):
if not root:
return root
q = deque([root])
while q:
size = len(q)
for i in range(size):
node = q.popleft()
if i < size - 1:
node.next = q[0]
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return root
print('BFS connect: O(n) time, O(w) space')Semakan Pantas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Ulang Kaji Pelajaran
Dalam pelajaran ini, anda telah mempelajari: definisi kelas TreeNode dan cara membina pepohon daripada tatasusunan, BFS mengikut aras menggunakan baris gilir hujung berganda dengan helah saiz aras untuk mengumpulkan nod, serta penggunaan termasuk kedalaman maksimum, kedalaman minimum, pandangan sebelah kanan, lintasan berselang-seli dan purata aras. Seterusnya, kita meneroka susunan lintasan DFS secara rekursif.
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Kelas TreeNode dan BFS Mengikut Aras” percuma?
Ya — teks penuh “Kelas TreeNode dan BFS Mengikut Aras” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Kelas TreeNode dan BFS Mengikut Aras”?
Bina pepohon binari daripada tatasusunan, laksanakan BFS dengan deque untuk mencetak mengikut aras dan selesaikan kedalaman maksimum menggunakan BFS. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 1 daripada 4.
Berapa lamakah pelajaran “Kelas TreeNode dan BFS Mengikut Aras” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Kelas TreeNode dan BFS Mengikut Aras
- DFS Dalam Susunan, Pra-Susunan dan Pasca-Susunan
- Diameter, Ketinggian dan Pepohon Seimbang
- Jumlah Laluan dan Leluhur Sepunya Terendah