Parcurgerea pe niveluri pune fiecare nod pe un nivel separat (lipsește len(coada))
BFS-ul scoate nodurile corect, dar nu știe unde se termină un nivel. La începutul fiecărui nivel, fixează câte noduri are: for _ in range(len(coada)):, scoate exact atâtea, iar copiii lor formează nivelul următor.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
O parcurgere în lățime (BFS) vizitează nodurile în ordinea corectă, nivel cu nivel, dar coada conține la un moment dat noduri de pe două niveluri: restul nivelului curent și copiii deja adăugați. Ca să grupezi rezultatul pe niveluri (pentru „parcurgere pe niveluri”, „vederea din dreapta”, „zigzag”, „adâncimea minimă”), trebuie să știi câte noduri aparțin nivelului curent.
Trucul standard: la începutul fiecărui nivel, len(coada) e exact numărul de noduri de pe acel nivel, pentru că toți copiii lor nu au fost încă adăugați. Scoți atâtea noduri, iar ce rămâne în coadă e nivelul următor.
Fără acest pas, primești fie un nivel per nod ([[1], [2], [3]]), fie toate nodurile într-un singur nivel. Python nu dă nicio eroare.
De ce apare: cauzele frecvente
1Un nivel nou pentru fiecare nod
while coada:
nod = coada.popleft()
rez.append([nod.val])
...while coada:
nivel = []
for _ in range(len(coada)):
nod = coada.popleft()
nivel.append(nod.val)
...
rez.append(nivel)range(len(coada)) e calculat o singură dată, la începutul nivelului, deci copiii adăugați între timp rămân pentru pasul următor.
2len(coada) recalculat în buclă
i = 0
while i < len(coada):
nod = coada.popleft()
...marime = len(coada)
for _ in range(marime):
nod = coada.popleft()
...Coada se schimbă în timpul nivelului; mărimea trebuie fixată înainte.
3Varianta cu perechi (nod, nivel)
coada = deque([rad])coada = deque([(rad, 0)])
# la adăugare: coada.append((copil, nivel + 1))Dacă păstrezi nivelul fiecărui nod, poți grupa după el fără să numeri.
Repară eroarea, direct în pagină
Funcția niveluri(rad) trebuie să returneze valorile arborelui grupate pe niveluri. Testul cu assert pică: fiecare nod ajunge pe un nivel separat. Repar-o ca să afișeze [[1], [2, 3], [4, 5]].
from collections import deque
class Nod:
def __init__(self, val, stanga=None, dreapta=None):
self.val = val
self.stanga = stanga
self.dreapta = dreapta
def niveluri(rad):
rez = []
coada = deque([rad])
while coada:
nivel = []
nod = coada.popleft()
nivel.append(nod.val)
if nod.stanga:
coada.append(nod.stanga)
if nod.dreapta:
coada.append(nod.dreapta)
rez.append(nivel)
return rez
rad = Nod(1, Nod(2, Nod(4)), Nod(3, None, Nod(5)))
rez = niveluri(rad)
assert rez == [[1], [2, 3], [4, 5]], f'niveluri gresite: {rez}'
print(rez)[[1], [2, 3], [4, 5]]
Indiciu
La începutul fiecărui nivel, scoate din coadă exact len(coada) noduri și adaugă-le într-o listă comună.
Reparația
from collections import deque
class Nod:
def __init__(self, val, stanga=None, dreapta=None):
self.val = val
self.stanga = stanga
self.dreapta = dreapta
def niveluri(rad):
rez = []
coada = deque([rad])
while coada:
nivel = []
for _ in range(len(coada)):
nod = coada.popleft()
nivel.append(nod.val)
if nod.stanga:
coada.append(nod.stanga)
if nod.dreapta:
coada.append(nod.dreapta)
rez.append(nivel)
return rez
rad = Nod(1, Nod(2, Nod(4)), Nod(3, None, Nod(5)))
rez = niveluri(rad)
assert rez == [[1], [2, 3], [4, 5]], f'niveluri gresite: {rez}'
print(rez)De ce merge
Varianta veche scotea un singur nod la fiecare pas al lui while și îi crea un nivel nou, deci rezultatul era [[1], [2], [3], [4], [5]]. Cu for _ in range(len(coada)), numărul de noduri al nivelului e fixat înainte să adaugi copiii: pe nivelul 2 sunt exact nodurile 2 și 3, iar copiii lor (4 și 5) rămân în coadă pentru nivelul următor.
Cum o eviți pe viitor
Ori de câte ori enunțul vorbește de „niveluri”, „adâncime” sau „distanță în pași”, scrie BFS-ul cu bucla interioară for _ in range(len(coada)) din prima. Testează pe un arbore cu trei niveluri, cu un nivel incomplet, și verifică numărul de liste din rezultat.
Întrebări frecvente
De ce len(coada) e corect la început?
La începutul nivelului, coada conține doar nodurile acelui nivel: copiii lor sunt adăugați abia când le procesezi. Numărul fixat înainte le separă exact.
Merge la fel pe grafuri?
Da. Același tipar dă distanța în pași de la start până la fiecare nod, de exemplu „în câte minute se strică toate fructele”.
Erori înrudite
BFS cu coada.pop() în loc de popleft(): distanțele ies prea mari pop() scoate ultimul element, deci coada ta funcționează ca o stivă și parcurgerea devine DFS. Nodurile sunt descoperite pe drumuri lungi și primesc distanțe prea mari. La BFS folosește deque și scoate cu popleft() (cel mai vechi element). AttributeError: 'NoneType' object has no attribute 'stanga' Funcția recursivă pe arbore a coborât într-un copil care nu există (None) și a cerut .stanga sau .val. Pune cazul de bază la început: if nod is None: return 0 (sau valoarea potrivită), înainte de orice acces la atributele nodului. RuntimeError: deque mutated during iteration Ai adăugat sau scos elemente dintr-un deque în timp ce îl parcurgeai cu for. Pentru o coadă BFS nu parcurge cu for: folosește while coada: nod = coada.popleft(), iar vecinii noi îi adaugi cu append. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
