...
Eroare Algoritmi și structuri de date · Arbori și heap-uri

Parcurgerea pe niveluri pune fiecare nod pe un nivel separat (lipsește len(coada))

Pe scurt

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

Greșit
PYTHON
while coada:
    nod = coada.popleft()
    rez.append([nod.val])
    ...
Corect
PYTHON
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ă

Greșit
PYTHON
i = 0
while i < len(coada):
    nod = coada.popleft()
    ...
Corect
PYTHON
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)

Greșit
PYTHON
coada = deque([rad])
Corect
PYTHON
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ă tu

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]].

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
[[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ă.

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.