Cod provocare: înțelegerea algoritmi binare copac în Swift
provocare: având în vedere un *non-gol* arbore binar, găsi suma maximă cale. Pentru această problemă, o cale este definită ca orice secvență de noduri de la un nod de pornire la orice nod din arbore de-a lungul conexiunilor părinte-copil. Calea trebuie să conțină cel puțin un nod și nu trebuie să treacă prin rădăcină:
Example #1:
Input:
4
/ \
5 6
Output: 15
Exemplul #2:
Input:
-10
/ \
9 20
/ \
15 7
Output: 42
provocarea
după cum indică și numele, un arbore binar este un tip popular de structură de date bazată pe arbori. Pentru a-și susține eficiența în timp și spațiu, copacii sunt adesea reprezentați de o cheie și de două sau mai multe noduri de frunze, similare cu următoarele structuri:
As one may guess, recursion is also a common property of tree-based structures. Chiar dacă majoritatea funcțiilor recursive sunt încruntate în aplicații reale, arborii permit anumite eficiențe, deoarece fiecare nod de frunze poate reprezenta și un alt arbore:
dacă nu sunt înțelese corect, copacii pot duce la confuzie, precum și la o complexitate adăugată. Pentru a rezolva provocarea noastră de cod, va trebui să concepem o metodă consecventă pentru navigarea arborelui nostru și o modalitate de a compara toate permutările posibile.
să lucrăm prin vizualizarea ideilor noastre înainte de a le angaja în cod. Pentru a începe, vom aborda mai întâi cum să navigați în copac. Deoarece structurile bazate pe arbori încorporează o proprietate conceptuală suplimentară de *adâncime*, tehnicile simple precum enumerarea rapidă nu sunt aplicate în mod normal. În schimb, putem folosi algoritmi traversali specifici, cum ar fi căutarea în adâncime sau lățime (de exemplu, DFS și respectiv BFS). Chiar dacă subiectul BFS este suficient de detaliat pentru o nouă discuție, putem concluziona că acesta ar fi modul normal în care s-ar traversa o astfel de structură. Cu toate acestea, deoarece lucrăm cu un arbore binar, putem aplica eficiențe algoritmice specifice pentru a ajuta la scurtarea procesului traversal.
deci, ce este un arbore binar? În esență, este o matrice standard care este vizualizată ca un copac. În acest caz, accentul este pus pe aspectele de vizualizare, deoarece acest lucru va afecta modul în care navigăm în structură. De exemplu, pentru fiecare nod, nodurile sale copil frunze stânga și dreapta pot fi de fapt calculate folosind aceste formule simple:
după cum sa discutat, aceste formule funcționează deoarece structura de bază pentru arborele nostru este o matrice. Aceasta diferă de alte structuri, cum ar fi un arbore B, Trie sau grafic, unde s-ar aplica o structură de date personalizată specifică pentru a reprezenta un model.
făcând comparații
deoarece arborele nostru binar nu este de fapt altceva decât o matrice, putem folosi într-adevăr enumerarea de bază pentru a itera prin toate valorile. Cu toate acestea, vom aplica formulele noastre pentru a determina nodurile noastre de frunze pentru copii. Odată stabilit, putem urmări totalurile fiecărui sub-arbore folosind o formă simplă de memorizare (de ex. programare dinamică).
Leave a Reply