Kode Utfordring: Forstå Binære Tre Algoritmer I Swift
Utfordring: Gitt en * ikke-tom * binær tre, finne maksimal bane sum. For dette problemet er en bane definert som en sekvens av noder fra noen startnode til en node i treet langs foreldre-barn-tilkoblinger. Banen må inneholde minst en node og trenger ikke å gå gjennom roten:
Example #1:
Input:
4
/ \
5 6
Output: 15
Eksempel #2:
Input:
-10
/ \
9 20
/ \
15 7
Output: 42
Utfordringen
som navnet indikerer, er et binært tre en populær type trebasert datastruktur. For å støtte deres tids-og romeffektivitet, er trær ofte representert av en nøkkel og to eller flere bladnoder, som ligner på følgende strukturer:
As one may guess, recursion is also a common property of tree-based structures. Selv om de fleste rekursive funksjoner er mislikt i reelle applikasjoner, trær tillate visse effektivitet som hver blad-node kan også representere et annet tre:
hvis ikke forstått riktig, kan trær føre til forvirring samt økt kompleksitet. For å løse kodeutfordringen må vi utarbeide en konsistent metode for å navigere i treet vårt og en måte å sammenligne alle mulige permutasjoner på.
La oss jobbe gjennom å visualisere våre ideer før du forplikter dem til å kode. For å starte, vil vi først ta opp hvordan du navigerer i treet. Siden trebaserte strukturer inneholder en ekstra konseptegenskap av * dybde*, brukes ikke enkle teknikker som hurtigopptelling normalt. I stedet kan vi bruke spesifikke traversale algoritmer som dybde eller bredde-første søk (f.eks. SELV OM TEMAET BFS er detaljert nok til en ny diskusjon, kan vi konkludere med at dette ville være den normale måten man ville krysse en slik struktur. Men siden vi jobber Med Et Binært Tre, kan vi bruke spesifikke algoritmiske effektiviteter for å hjelpe snarvei traversal prosessen.
Så, hva Er Et Binært Tre? I hovedsak er det en standard Array som er visualisert som et tre. I dette tilfellet legges det vekt på visualiseringsaspektene siden dette vil påvirke hvordan vi navigerer i strukturen. For eksempel, for hver node, kan dens venstre og høyre bladbarnnoder faktisk beregnes ved hjelp av disse enkle formlene:
som diskutert fungerer disse formlene fordi den underliggende strukturen for Treet vårt er En Matrise. Dette skiller seg fra andre strukturer som Et b-tre, Trie eller Graf der man ville bruke en bestemt tilpasset datastruktur for å representere en modell.
Å Gjøre Sammenligninger
siden Vårt Binære Tre faktisk ikke er noe mer enn En Matrise, kan vi faktisk bruke grunnleggende opplisting for å iterere gjennom alle verdier. Vi bruker imidlertid våre formler for å bestemme våre barnbladnoder. Når vi er etablert, kan vi spore totalene til hvert subtre ved hjelp av en enkel form for memoisering (f.eks. dynamisk programmering).
Leave a Reply