Parcurgerea în inordine returnează doar rădăcina: rezultatele apelurilor recursive sunt ignorate
Funcția apelează inordine(nod.stanga) și inordine(nod.dreapta), dar nu folosește ce returnează, deci rezultatul conține doar valoarea nodului curent. Combină rezultatele: return inordine(nod.stanga) + [nod.val] + inordine(nod.dreapta).
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Într-o funcție recursivă care returnează un rezultat, fiecare apel își construiește propria listă. Dacă scrii inordine(nod.stanga) pe o linie separată, lista construită de subarborele stâng e calculată și apoi aruncată, pentru că nimeni nu o salvează.
Simptomul tipic: parcurgerea unui arbore cu multe noduri returnează [5], adică doar rădăcina. Nu apare nicio eroare, pentru că toate apelurile rulează corect, doar că rezultatele lor nu ajung nicăieri.
Ai două variante corecte: fie combini explicit rezultatele (stanga + [val] + dreapta), fie folosești o singură listă comună, transmisă ca parametru sau definită într-o funcție exterioară, la care fiecare apel adaugă cu append. Nu le amesteca: dacă folosești lista comună, apelurile nu mai trebuie să returneze nimic.
De ce apare: cauzele frecvente
1Rezultatul apelurilor recursive nu e folosit
inordine(nod.stanga)
rez = [nod.val]
inordine(nod.dreapta)
return rezreturn inordine(nod.stanga) + [nod.val] + inordine(nod.dreapta)Fiecare apel returnează lista subarborelui lui, iar concatenarea le pune în ordinea stânga, rădăcină, dreapta.
2Varianta cu listă comună
def inordine(nod):
rez = []
if nod:
inordine(nod.stanga)
rez.append(nod.val)
inordine(nod.dreapta)
return rezdef inordine(nod, rez):
if nod:
inordine(nod.stanga, rez)
rez.append(nod.val)
inordine(nod.dreapta, rez)
return rezToate apelurile adaugă în aceeași listă rez, transmisă mai departe, deci nimic nu se pierde. E și mai eficientă, pentru că nu copiază liste.
Repară eroarea, direct în pagină
Funcția inordine(nod) trebuie să returneze valorile unui arbore binar de căutare în ordine crescătoare. Testul cu assert pică: rezultatul conține doar rădăcina. Repar-o ca să afișeze [1, 3, 5, 8].
class Nod:
def __init__(self, val, stanga=None, dreapta=None):
self.val = val
self.stanga = stanga
self.dreapta = dreapta
def inordine(nod):
if nod is None:
return []
inordine(nod.stanga)
rez = [nod.val]
inordine(nod.dreapta)
return rez
radacina = Nod(5, Nod(3, Nod(1)), Nod(8))
rez = inordine(radacina)
assert rez == [1, 3, 5, 8], f'parcurgere incompleta: {rez}'
print(rez)[1, 3, 5, 8]
Indiciu
Combină listele returnate de cele două apeluri recursive cu valoarea nodului curent.
Reparația
class Nod:
def __init__(self, val, stanga=None, dreapta=None):
self.val = val
self.stanga = stanga
self.dreapta = dreapta
def inordine(nod):
if nod is None:
return []
return inordine(nod.stanga) + [nod.val] + inordine(nod.dreapta)
radacina = Nod(5, Nod(3, Nod(1)), Nod(8))
rez = inordine(radacina)
assert rez == [1, 3, 5, 8], f'parcurgere incompleta: {rez}'
print(rez)De ce merge
Apelurile inordine(nod.stanga) și inordine(nod.dreapta) calculau corect listele subarborilor, dar rezultatul lor era aruncat, iar funcția returna doar [nod.val], adică [5] pentru rădăcină. Concatenarea stanga + [val] + dreapta folosește ce returnează fiecare apel: subarborele stâng dă [1, 3], cel drept [8], iar rezultatul final e [1, 3, 5, 8].
Cum o eviți pe viitor
La orice funcție recursivă, întreabă-te ce faci cu valoarea returnată de fiecare apel recursiv. Dacă apelul stă singur pe o linie, fără return, atribuire sau +, rezultatul lui se pierde, cu excepția cazului în care funcția modifică o structură comună. Testează pe un arbore cu cel puțin trei niveluri și verifică lungimea rezultatului față de numărul de noduri.
Întrebări frecvente
Care variantă e mai bună?
Cea cu listă comună face O(n) operații în total. Cea cu concatenare copiază liste la fiecare nivel, deci poate ajunge la O(n²) pe arbori dezechilibrați, dar e mai scurtă. Pentru arbori mici, amândouă sunt în regulă.
Cum fac preordinea sau postordinea?
Schimbi doar poziția lui [nod.val]: preordine = [val] + stanga + dreapta, postordine = stanga + dreapta + [val].
Erori înrudite
Inserarea în BST pierde nodurile noi: rezultatul apelului recursiv nu e atribuit Funcția recursivă returnează nodul nou când ajunge la None, dar dacă nu scrii rad.stanga = insereaza(rad.stanga, val), nodul nu e legat de arbore. Atribuie rezultatul la fiecare nivel și la apelul de sus (rad = insereaza(rad, val)). TypeError: unsupported operand type(s) for +: 'int' and 'NoneType' Ai adunat un număr cu rezultatul unei funcții care a returnat None: de obicei o funcție recursivă care, într-o ramură, face apelul recursiv fără return în fața lui. Pune return pe fiecare ramură a funcției. 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. Î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.
