Klasa TreeNode i BFS poziomami
Zbudują Państwo drzewa binarne z tablic, zaimplementują BFS z deque do wypisywania poziomami i rozwiążą problem maksymalnej głębokości za pomocą BFS.
Klasa TreeNode i BFS poziomami to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Podstawy klasy TreeNode
Drzewo binarne to hierarchiczna struktura danych, w której każdy węzeł ma co najwyżej dwoje dzieci, nazywanych lewym i prawym. W Pythonie modelujemy węzeł za pomocą prostej klasy: class TreeNode: def __init__(self, val=0, left=None, right=None). Każdy problem dotyczący drzew podczas rozmowy kwalifikacyjnej zaczyna się od tej definicji — można ją znaleźć w kodzie bazowym niemal każdego zadania dotyczącego drzew w 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)Budowanie drzew z tablic
W zadaniach rekrutacyjnych często otrzymuje się drzewo reprezentowane jako tablica w kolejności poziomów, w której None oznacza brakujący węzeł. Dla indeksu i lewe dziecko znajduje się pod indeksem 2i+1, a prawe pod indeksem 2i+2. Napisanie funkcji pomocniczej deserializującej tę tablicę do połączonych węzłów TreeNode jest cennym narzędziem, które oszczędza czas podczas ćwiczeń.
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)Czym jest BFS i dlaczego używamy kolejki
Przeszukiwanie wszerz (BFS) odwiedza wszystkie węzły na głębokości d, zanim odwiedzi którykolwiek węzeł na głębokości d+1. To przechodzenie poziomami jest dokładnie tym, co zapewnia kolejka (FIFO): umieszczamy korzeń w kolejce, a następnie przetwarzamy węzły pojedynczo, dodając po drodze do kolejki dzieci każdego węzła. Pythonowy obiekt collections.deque zapewnia operacje appendleft i popleft w czasie O(1), dlatego jest właściwym wyborem zamiast zwykłej listy.
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 w kolejności poziomów: grupowanie według poziomów
Standardowy wariant BFS grupuje węzły według poziomów, zapisując rozmiar kolejki na początku każdej iteracji. Należy przetworzyć dokładnie tyle węzłów, zebrać ich wartości, a następnie przejść do kolejnego poziomu. W wyniku otrzymujemy listę list — bardzo częsty format wyniku w zadaniach rekrutacyjnych, takich jak przechodzenie drzewa binarnego poziomami, przechodzenie zygzakowate i widok drzewa od prawej strony.
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]]Maksymalna głębokość za pomocą BFS
Maksymalna głębokość drzewa binarnego jest równa liczbie poziomów w jego przechodzeniu BFS. Wystarczy policzyć, ile razy kończy się pętla przetwarzająca poziom. Otrzymujemy rozwiązanie o złożoności czasowej O(n) i pamięciowej O(w), gdzie w jest maksymalną szerokością drzewa. Dla drzewa zrównoważonego w jest rzędu O(n/2), więc w najgorszym przypadku złożoność pamięciowa wynosi 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)) # 3Widok drzewa binarnego od prawej strony
Widok drzewa od prawej strony zwraca ostatni widoczny węzeł, gdy patrzymy na drzewo z prawej — czyli ostatni element każdego poziomu podczas przechodzenia BFS. Jest to bezpośrednie zastosowanie BFS w kolejności poziomów: należy zebrać ostatni węzeł w każdej iteracji przetwarzającej poziom. Złożoność czasowa wynosi O(n), a pamięciowa O(w) dla kolejki.
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]Przejście zygzakowe według poziomów
W przejściu zygzakowym węzły na nieparzystych poziomach są zbierane od lewej do prawej, a na parzystych — od prawej do lewej. Najczytelniejsza implementacja pozostawia kolejkę BFS bez zmian i po prostu odwraca listy naprzemiennych poziomów przed dołączeniem ich do wyniku. Kierunek należy śledzić za pomocą flagi typu boolean, zmieniając jej wartość po każdym poziomie. Pozwala to uniknąć złożoności związanej z użyciem kolejki dwustronnej w pętli wewnętrznej.
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))Analiza złożoności pamięciowej BFS
BFS wykorzystuje O(w) pamięci, gdzie w oznacza maksymalną szerokość drzewa. W przypadku pełnego drzewa binarnego z n węzłami ostatni poziom ma (n+1)/2 węzłów, więc kolejka BFS może jednocześnie przechowywać nawet n/2 węzłów. Oznacza to, że pod względem pamięci BFS wypada gorzej niż DFS (O(h)) dla szerokich, zrównoważonych drzew, ale lepiej dla głębokich, silnie niezrównoważonych drzew, w których głębokość stosu wywołań DFS jest równa 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')Średnia wartości na poziomach drzewa binarnego
Obliczanie średniej wartości na każdym poziomie to kolejne bezpośrednie zastosowanie BFS. Należy zsumować wszystkie wartości na danym poziomie, podzielić sumę przez liczbę węzłów i dodać wynik do listy wyników. To zadanie sprawdza, czy potrafisz wykonywać działania arytmetyczne wewnątrz pętli przetwarzającej poziom. W Pythonie 3 należy zawsze używać dzielenia zmiennoprzecinkowego (/), a przypadek pustego drzewa obsłużyć na początku.
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]Minimalna głębokość za pomocą BFS
Minimalna głębokość to odległość od korzenia do najbliższego węzła liścia (węzła bez dzieci). BFS znajduje ją optymalnie: pierwszy napotkany podczas przechodzenia poziomami węzeł liść z pewnością znajduje się na minimalnej głębokości. Bieżącą głębokość należy zwrócić natychmiast po napotkaniu liścia. W najgorszym przypadku złożoność wynosi O(n), ale dla zrównoważonych drzew algorytm często kończy działanie znacznie wcześniej.
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)) # 2Łączenie sąsiadów na tym samym poziomie
Zadanie populate next-right pointers polega na połączeniu każdego węzła z jego prawym sąsiadem na tym samym poziomie. W przypadku BFS jest to proste: w pętli przetwarzającej każdy poziom należy ustawić node.next = q[0] dla wszystkich węzłów oprócz ostatniego. To klasyczny przykład zadania, w którym BFS sprawia, że rozwiązanie staje się oczywiste, podczas gdy DFS wymaga uważnego śledzenia wskaźników między poddrzewami.
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')Szybki test
Sprawdź swoją znajomość zagadnień Data Structures & Algorithms — Coding Interview Prep z tego rozdziału.
Podsumowanie lekcji
W tej lekcji poznano: definicję klasy TreeNode oraz sposób budowania drzew z tablic, BFS poziomami z użyciem deque i sztuczkę z rozmiarem poziomu służącą do grupowania węzłów, a także zastosowania obejmujące maksymalną głębokość, minimalną głębokość, widok prawej strony, przejście zygzakowe i średnią wartości na poziomach. Następnie omówione zostaną porządki rekurencyjnego przechodzenia DFS.
Często zadawane pytania
Czy lekcja „Klasa TreeNode i BFS poziomami” jest bezpłatna?
Tak — pełny tekst „Klasa TreeNode i BFS poziomami” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Klasa TreeNode i BFS poziomami”?
Zbudują Państwo drzewa binarne z tablic, zaimplementują BFS z deque do wypisywania poziomami i rozwiążą problem maksymalnej głębokości za pomocą BFS. Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.
Ile czasu zajmuje lekcja „Klasa TreeNode i BFS poziomami”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Klasa TreeNode i BFS poziomami
- DFS w kolejności inorder, preorder i postorder
- Średnica, wysokość i drzewa zrównoważone
- Suma ścieżki i najniższy wspólny przodek