Drum de la rădăcină la frunză cu suma dată
O aplicație de trasee montane memorează potecile ca un arbore: fiecare bifurcație e un nod, iar fiecare porțiune are o durată. Există un traseu complet (până la un capăt de potecă) care durează exact 22 de minute? Problema se rezolvă cu o parcurgere în adâncime în care scazi valoarea fiecărui nod din țintă, iar pentru toate drumurile adaugi backtracking.
Problema
Primești rădăcina unui arbore binar cu numere întregi și o sumă țintă. Un drum rădăcină–frunză pornește din rădăcină și coboară până la o frunză (un nod fără copii). Vrem să știm două lucruri:
Scrie funcțiile are_drum(radacina, suma) (returnează True/False) și drumuri(radacina, suma) (returnează lista tuturor drumurilor rădăcină–frunză cu suma dată, de la stânga la dreapta). Clasa Nod, funcția construieste și testele sunt deja sc…
- are_drum: scazi valoarea nodului din țintă și verifici rest == 0 doar la frunze.
- drumuri: o funcție interioară dfs(nod, rest, drum) cu append / pop și list(drum) la salvare.
- Trebuie să apară: True, True, False, False, [[5, 4, 11, 2], [5, 8, 4, 5]], [[5, 8, 4, 1]], [].
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan