Kodutmaning: förstå binära Trädalgoritmer i Swift
utmaning: givet ett *icke-tomt* binärt träd, hitta den maximala sökvägsbeloppet. För detta problem definieras en sökväg som vilken sekvens av noder som helst från någon startnod till vilken nod som helst i trädet längs föräldra-barnanslutningarna. Sökvägen måste innehålla minst en nod och behöver inte gå igenom roten:
Example #1:
Input:
4
/ \
5 6
Output: 15
exempel #2:
Input:
-10
/ \
9 20
/ \
15 7
Output: 42
utmaningen
som namnet antyder är ett binärt träd en populär typ av trädbaserad datastruktur. För att stödja deras tid och rymdeffektivitet representeras träd ofta av en nyckel och två eller flera bladnoder, liknande följande strukturer:
As one may guess, recursion is also a common property of tree-based structures. Även om de flesta rekursiva funktioner är rynkade på i verkliga applikationer tillåter träd vissa effektivitetsvinster eftersom varje bladnod också kan representera ett annat träd:
om det inte förstås korrekt kan träd leda till förvirring och ökad komplexitet. För att lösa vår kodutmaning måste vi utarbeta en konsekvent metod för att navigera i vårt träd och ett sätt att jämföra alla möjliga permutationer.
Låt oss arbeta genom att visualisera våra ideer innan vi förbinder dem att koda. För att börja, ska vi först ta itu med hur man navigerar i trädet. Eftersom trädbaserade strukturer innehåller en ytterligare konceptegenskap av * djup*, tillämpas inte enkla tekniker som snabbräkning normalt. Istället kan vi använda specifika traversalalgoritmer som djup eller bredd-första sökning (t.ex. DFS respektive BFS). Även om ämnet BFS är tillräckligt detaljerat för en ny diskussion, kan vi dra slutsatsen att detta skulle vara det normala sättet man skulle korsa en sådan struktur. Men eftersom vi arbetar med ett binärt träd kan vi tillämpa specifika algoritmiska effektivitetsvinster för att hjälpa till att genvägera traversprocessen.
Så, vad är ett binärt träd? I huvudsak är det en standardmatris som visualiseras som ett träd. I detta fall läggs tonvikten på visualiseringsaspekterna eftersom detta kommer att påverka hur vi navigerar i strukturen. Till exempel för varje nod kan dess vänstra och högra bladbarnnoder faktiskt beräknas med hjälp av dessa enkla formler:
som diskuterats fungerar dessa formler eftersom den underliggande strukturen för vårt träd är en matris. Detta skiljer sig från andra strukturer som ett B-träd, försök eller Diagram där man skulle tillämpa en specifik anpassad datastruktur för att representera en modell.
göra jämförelser
eftersom vårt binära träd faktiskt inte är något annat än en matris, kan vi verkligen använda grundläggande uppräkning för att iterera genom alla värden. Vi tillämpar dock våra formler för att bestämma våra barnbladsnoder. När vi väl är etablerade kan vi spåra summan av varje underträd med hjälp av en enkel form av memoisering (t.ex. dynamisk programmering).
Leave a Reply