kihívás: adott egy * nem üres * bináris fa, keresse meg a maximális útvonal összege. Ehhez a problémához az elérési utat úgy definiáljuk, mint a csomópontok bármely sorozatát a kiindulási csomóponttól a fa bármely csomópontjáig a szülő-gyermek kapcsolatok mentén. Az útvonalnak legalább egy csomópontot kell tartalmaznia, és nem kell a gyökéren keresztül mennie:

Example #1:
Input: 
4
/ \
5 6
Output: 15

példa #2:

Input: 
-10
/ \
9 20
/ \
15 7
Output: 42

the Challenge

ahogy a neve is jelzi, a bináris fa alapú adatstruktúra népszerű típusa. Az idő-és térhatékonyságuk támogatása érdekében a fákat gyakran egy kulcs és két vagy több levélcsomó képviseli, hasonlóan a következő struktúrákhoz:

As one may guess, recursion is also a common property of tree-based structures. Bár a legtöbb rekurzív függvények elkomorodott valós alkalmazások, fák lehetővé bizonyos hatékonyságjavulás, mint egyes falevél-csomópont is képviseli egy másik fa:

ha nem értik helyesen, a fák zavart okozhatnak, valamint összetettebbé válhatnak. A kód kihívásának megoldásához ki kell dolgoznunk egy következetes módszert a fa navigálására, valamint az összes lehetséges permutáció összehasonlítására.

dolgozzunk az ötleteink megjelenítésén, mielőtt kódolásra kötelezzük őket. A kezdéshez először foglalkozunk a fa navigálásával. Mivel a fa alapú struktúrák tartalmaznak egy további koncepció tulajdonságot *mélység*, az egyszerű technikákat, mint például a gyors felsorolást, általában nem alkalmazzák. Ehelyett olyan speciális keresztirányú algoritmusokat használhatunk, mint a mélység vagy a szélességi első keresés (például DFS vagy BFS). Annak ellenére, hogy a BFS témája elég részletes egy új beszélgetéshez, arra a következtetésre juthatunk, hogy ez lenne a normális út egy ilyen struktúra áthaladásához. Mivel azonban egy bináris fával dolgozunk, speciális algoritmikus hatékonyságot alkalmazhatunk a keresztirányú folyamat gyorsbillentyűjének segítésére.

Tehát mi a bináris fa? Lényegében ez egy szabványos tömb, amely fa formájában jelenik meg. Ebben az esetben a vizualizációs szempontokra helyezik a hangsúlyt, mivel ez befolyásolja a struktúra navigálását. Például minden csomópont esetében a bal és a jobb oldali gyermekcsomópontok ténylegesen kiszámíthatók ezekkel az egyszerű képletekkel:

amint azt tárgyaltuk, ezek a képletek azért működnek, mert a fa mögöttes szerkezete tömb. Ez különbözik más struktúráktól, mint például a B-fa, a Trie vagy a gráf, ahol egy adott egyedi adatstruktúrát alkalmaznánk egy modell ábrázolására.

összehasonlítások készítése

mivel bináris fánk valójában nem más, mint egy tömb, valóban felhasználhatjuk az alapvető felsorolást az összes érték iterálására. Azonban fogjuk alkalmazni a képleteket, hogy meghatározzák a gyermek levél csomópontok. Miután létrehoztuk, nyomon követhetjük az egyes Alfák összességét a memoizáció egyszerű formájával (pl. dinamikus programozás).