Challenge: dato un albero binario * non vuoto*, trova la somma massima del percorso. Per questo problema, un percorso è definito come qualsiasi sequenza di nodi da un nodo iniziale a qualsiasi nodo nell’albero lungo le connessioni padre-figlio. Il percorso deve contenere almeno un nodo e non deve passare attraverso la radice:

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

Esempio #2:

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

La sfida

Come indica il nome, un albero binario è un tipo popolare di struttura dati basata su albero. Per supportare le loro efficienze temporali e spaziali, gli alberi sono spesso rappresentati da una chiave e due o più nodi foglia, simili alle seguenti strutture:

As one may guess, recursion is also a common property of tree-based structures. Anche se la maggior parte delle funzioni ricorsive sono malviste in applicazioni reali, alberi di consentire una maggiore efficienza in quanto ogni nodo foglia può anche rappresentare un altro albero:

Se non compresi correttamente, gli alberi possono portare a confusione e complessità aggiunta. Per risolvere la nostra sfida di codice, dovremo elaborare un metodo coerente per navigare nel nostro albero e un modo per confrontare tutte le possibili permutazioni.

Lavoriamo attraverso la visualizzazione delle nostre idee prima di impegnarle nel codice. Per iniziare, affronteremo prima come navigare nell’albero. Poiché le strutture ad albero incorporano una proprietà concettuale aggiuntiva di * depth*, le tecniche semplici come l’enumerazione rapida non vengono normalmente applicate. Invece, possiamo utilizzare specifici algoritmi di attraversamento come la ricerca di profondità o ampiezza (ad esempio DFS e BFS rispettivamente). Anche se l’argomento di BFS è abbastanza dettagliato per una nuova discussione, possiamo concludere che questo sarebbe il modo normale in cui si attraverserebbe una tale struttura. Tuttavia, poiché stiamo lavorando con un albero binario, possiamo applicare specifiche efficienze algoritmiche per aiutare a abbreviare il processo di attraversamento.

Quindi, cos’è un albero binario? Essenzialmente, è un array standard che viene visualizzato come un albero. In questo caso, l’enfasi è posta sugli aspetti di visualizzazione poiché ciò influenzerà il modo in cui navighiamo nella struttura. Ad esempio, per ogni nodo, i suoi nodi figlio foglia sinistra e destra possono essere calcolati utilizzando queste semplici formule:

Come discusso, queste formule funzionano perché la struttura sottostante per il nostro albero è un Array. Questo differisce da altre strutture come un albero B, un Trie o un grafico in cui si applicherebbe una specifica struttura dati personalizzata per rappresentare un modello.

Fare confronti

Poiché il nostro albero binario non è in realtà altro che un Array, possiamo effettivamente usare l’enumerazione di base per scorrere tutti i valori. Tuttavia, applicheremo le nostre formule per determinare i nostri nodi foglia figlio. Una volta stabilito, siamo in grado di monitorare i totali di ogni sotto-albero utilizzando una semplice forma di memoizzazione (ad es. programmazione dinamica).