Kelas TreeNode dan BFS Berdasarkan Level
Bangun pohon biner dari array, implementasikan BFS dengan deque untuk mencetak tiap level, dan selesaikan maximum-depth menggunakan BFS.
Kelas TreeNode dan BFS Berdasarkan Level adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Dasar Kelas TreeNode
Pohon biner adalah struktur data hierarkis yang setiap simpulnya memiliki paling banyak dua anak, yang disebut kiri dan kanan. Dalam Python, kita memodelkan simpul dengan kelas sederhana: class TreeNode: def __init__(self, val=0, left=None, right=None). Setiap masalah pohon dalam wawancara dimulai dengan definisi ini—Anda akan melihatnya dalam hampir setiap kode kerangka masalah pohon 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)Membangun Pohon dari Larik
Soal wawancara sering memberikan pohon yang direpresentasikan sebagai larik urutan tingkat, dengan None menandai simpul yang hilang. Diberikan indeks i, anak kiri berada pada 2i+1 dan anak kanan pada 2i+2. Menulis fungsi pembantu untuk mendeserialisasi larik ini menjadi TreeNodes tertaut adalah utilitas berharga yang menghemat waktu selama 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)Apa Itu BFS dan Mengapa Menggunakan Antrean?
Penelusuran Melebar-Pertama (BFS) mengunjungi semua simpul pada kedalaman d sebelum mengunjungi simpul mana pun pada kedalaman d+1. Penelusuran tingkat demi tingkat ini persis seperti yang diberikan oleh antrean (FIFO): kita memasukkan akar ke antrean, lalu memproses simpul satu per satu sambil memasukkan anak setiap simpul ke antrean. Python menyediakan collections.deque dengan appendleft dan popleft berkompleksitas O(1), sehingga menjadi pilihan yang tepat daripada larik 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 Urutan Tingkat: Mengelompokkan Berdasarkan Tingkat
Varian BFS standar mengelompokkan simpul ke dalam tingkat dengan mencatat ukuran antrean pada awal setiap iterasi. Proses tepat sejumlah simpul tersebut, kumpulkan nilainya, lalu lanjutkan ke tingkat berikutnya. Hasilnya adalah daftar-daftar—format keluaran yang sangat umum dalam wawancara untuk masalah seperti penelusuran tingkat-per-tingkat pohon biner, penelusuran zig-zag, dan tampilan 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 pohon biner sama dengan jumlah tingkat dalam penelusuran BFS. Hitung saja berapa kali Anda menyelesaikan perulangan tingkat. Ini menghasilkan solusi dengan waktu O(n) dan ruang O(w), dengan w sebagai lebar maksimum pohon. Untuk pohon seimbang, w adalah O(n/2), sehingga ruang pada kasus terburuk adalah 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)) # 3Tampilan Sisi Kanan Pohon Biner
Tampilan sisi kanan mengembalikan simpul terakhir yang terlihat ketika Anda melihat pohon dari kanan—yaitu, elemen terakhir pada setiap tingkat dalam penelusuran BFS. Ini adalah penerapan langsung BFS urutan tingkat: kumpulkan simpul terakhir dalam setiap perulangan tingkat. Kompleksitas waktunya O(n), sedangkan ruangnya O(w) untuk antrean.
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]Penelusuran Berdasarkan Tingkat secara Zigzag
Dalam penelusuran zigzag, tingkat ganjil dikumpulkan dari kiri ke kanan dan tingkat genap dari kanan ke kiri. Implementasi paling rapi mempertahankan antrean BFS tanpa perubahan dan cukup membalik daftar tingkat secara bergantian sebelum menambahkannya ke hasil. Lacak arah dengan penanda benar/salah yang dibalik pada setiap tingkat. Ini menghindari kompleksitas antrean dua ujung dalam perulangan bagian dalam.
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 Kompleksitas Ruang BFS
BFS menggunakan ruang O(w), dengan w sebagai lebar maksimum pohon. Untuk pohon biner sempurna dengan n simpul, tingkat terakhir memiliki (n+1)/2 simpul—sehingga BFS dapat menampung hingga n/2 simpul dalam antrean secara bersamaan. Hal ini membuat BFS lebih buruk dalam penggunaan ruang daripada DFS (O(h)) untuk pohon seimbang dengan lebar besar, tetapi lebih baik untuk pohon miring yang dalam, ketika kedalaman tumpukan pemanggilan DFS sama dengan 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')Rata-rata Tingkat pada Pohon Biner
Menghitung nilai rata-rata di setiap tingkat adalah penerapan langsung BFS lainnya. Jumlahkan semua nilai pada suatu tingkat, bagi dengan banyaknya nilai, lalu tambahkan ke daftar hasil. Soal ini menguji apakah Anda dapat melakukan aritmetika dalam perulangan tingkat. Selalu gunakan pembagian float di Python 3 (operator /), dan tangani kasus khusus pohon kosong di awal.
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 adalah jarak dari akar ke simpul daun terdekat (simpul yang tidak memiliki anak). BFS menemukannya secara optimal: simpul daun pertama yang ditemui selama penelusuran berdasarkan tingkat dijamin berada pada kedalaman minimum. Kembalikan kedalaman saat ini segera setelah menemukan simpul daun. Kompleksitasnya O(n) dalam kasus terburuk, tetapi sering kali berhenti jauh lebih awal untuk pohon 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 Simpul Bersaudara pada Tingkat yang Sama
Masalah mengisi penunjuk ke kanan berikutnya meminta Anda menghubungkan setiap simpul ke tetangga kanannya pada tingkat yang sama. Dengan BFS, hal ini mudah dilakukan: dalam setiap perulangan tingkat, tetapkan node.next = q[0] untuk semua simpul kecuali simpul terakhir. Ini adalah contoh klasik ketika BFS membuat solusi terlihat jelas, sedangkan DFS memerlukan pelacakan penunjuk yang cermat di seluruh subpohon.
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')Uji Cepat
Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda mempelajari: definisi kelas TreeNode dan cara membangun pohon dari larik, BFS berdasarkan tingkat menggunakan antrean dengan trik ukuran tingkat untuk mengelompokkan simpul, serta penerapan termasuk kedalaman maksimum, kedalaman minimum, tampilan sisi kanan, penelusuran zigzag, dan rata-rata tingkat. Selanjutnya, kita akan mempelajari urutan penelusuran DFS rekursif.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Kelas TreeNode dan BFS Berdasarkan Level” gratis?
Ya — teks lengkap “Kelas TreeNode dan BFS Berdasarkan Level” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Kelas TreeNode dan BFS Berdasarkan Level”?
Bangun pohon biner dari array, implementasikan BFS dengan deque untuk mencetak tiap level, dan selesaikan maximum-depth menggunakan BFS. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Kelas TreeNode dan BFS Berdasarkan Level” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Kelas TreeNode dan BFS Berdasarkan Level
- DFS In-Order, Pre-Order, dan Post-Order
- Diameter, Tinggi, dan Pohon Seimbang
- Jumlah Jalur dan Leluhur Bersama Terendah