Kodeudfordring: forståelse af binære Træalgoritmer i hurtig
udfordring: givet et *ikke-tomt* binært træ, find den maksimale sti sum. For dette problem defineres en sti som en hvilken som helst sekvens af noder fra en startknude til en hvilken som helst knude i træet langs forældre-barn-forbindelserne. Stien skal indeholde mindst en node og behøver ikke at gå gennem roden:
Example #1:
Input:
4
/ \
5 6
Output: 15
eksempel #2:
Input:
-10
/ \
9 20
/ \
15 7
Output: 42
udfordringen
som navnet antyder, er et binært træ en populær type træbaseret datastruktur. For at understøtte deres tids-og rumeffektivitet er træer ofte repræsenteret af en nøgle og to eller flere bladknuder, der ligner følgende strukturer:
As one may guess, recursion is also a common property of tree-based structures. Selvom de fleste rekursive funktioner er forkert i rigtige applikationer, tillader træer visse effektiviteter, da hver bladknude også kan repræsentere et andet træ:
Hvis det ikke forstås korrekt, kan træer føre til forvirring såvel som tilføjet kompleksitet. For at løse vores kodeudfordring skal vi udtænke en ensartet metode til at navigere i Vores træ og en måde at sammenligne alle mulige permutationer på.
lad os arbejde gennem visualisering af vores ideer, før vi forpligter dem til kode. For at starte, vil vi først tage fat på, hvordan man navigerer i træet. Da træbaserede strukturer indeholder en ekstra konceptegenskab af * dybde*, anvendes enkle teknikker som hurtigtælling normalt ikke. I stedet kan vi bruge specifikke traversalalgoritmer som dybde eller bredde-første søgning (f. eks. Selvom emnet BFS er detaljeret nok til en ny diskussion, kan vi konkludere, at dette ville være den normale måde, man ville krydse en sådan struktur på. Men da vi arbejder med et binært træ, kan vi anvende specifikke algoritmiske effektivitetsgevinster for at hjælpe genvej gennemløbsprocessen.
så hvad er et binært træ? I det væsentlige er det et standard Array, der visualiseres som et træ. I dette tilfælde lægges der vægt på visualiseringsaspekterne, da dette vil påvirke, hvordan vi navigerer i strukturen. For hver node kan dens venstre og højre bladbarnoder faktisk beregnes ved hjælp af disse enkle formler:
som diskuteret fungerer disse formler, fordi den underliggende struktur for vores træ er et Array. Dette adskiller sig fra andre strukturer som et B-træ, Trie eller graf, hvor man ville anvende en bestemt brugerdefineret datastruktur til at repræsentere en model.
sammenligning
da vores binære træ faktisk ikke er andet end et Array, kan vi faktisk bruge grundlæggende optælling til at gentage gennem alle værdier. Vi anvender dog vores formler til at bestemme vores børnebladnoder. Når det er etableret, kan vi spore totalerne for hvert undertræ ved hjælp af en simpel form for memoisering (f.eks. dynamisk programmering).
Leave a Reply