Challenge: gegeven een* niet-lege * binaire boom, zoek de maximale padsom. Voor dit probleem wordt een pad gedefinieerd als elke opeenvolging van knopen van een startknooppunt naar een knooppunt in de boomstructuur langs de ouder-kindverbindingen. Het pad moet minstens één knooppunt bevatten en hoeft niet door de root te gaan:

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

Voorbeeld #2:

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

de Challenge

zoals de naam al aangeeft, is een binaire boom een populair type boomgebaseerde datastructuur. Om hun tijd-en ruimteefficiëntie te ondersteunen, worden bomen vaak vertegenwoordigd door een sleutel en twee of meer bladknopen, vergelijkbaar met de volgende structuren:

As one may guess, recursion is also a common property of tree-based structures. Hoewel de meeste recursieve functies zijn afgekeurd in echte toepassingen, bomen toestaan voor bepaalde efficiëntie als elk blad-knooppunt kan ook verwijzen naar een andere boom:

indien niet correct begrepen, kunnen bomen leiden tot verwarring en extra complexiteit. Om onze codeuitdaging op te lossen, moeten we een consistente methode bedenken voor het navigeren in onze boom en een manier om alle mogelijke permutaties te vergelijken.

laten we onze ideeën visualiseren voordat we ze committen naar code. Om te beginnen zullen we eerst bespreken hoe je door de boom kunt navigeren. Omdat tree-based structuren een extra concept eigenschap van *depth * bevatten, worden eenvoudige technieken zoals fast-enumeration normaal gesproken niet toegepast. In plaats daarvan kunnen we specifieke traversale algoritmen gebruiken, zoals diepte of breedte-eerste zoekopdracht (bijvoorbeeld DFS en BFS respectievelijk). Hoewel het onderwerp van BFS gedetailleerd genoeg is voor een nieuwe discussie, kunnen we concluderen dat dit de normale manier zou zijn om een dergelijke structuur te doorkruisen. Omdat we echter met een binaire boom werken, kunnen we specifieke algoritmische efficiëntie toepassen om het traversale proces te helpen verkorten.

dus, wat is een binaire boom? In wezen is het een standaard Array die wordt gevisualiseerd als een boom. In dit geval wordt de nadruk gelegd op de visualisatie-aspecten omdat dit van invloed zal zijn op hoe we door de structuur navigeren. Bijvoorbeeld, voor elk knooppunt, zijn linker en rechter blad kind knooppunten kunnen eigenlijk worden berekend met behulp van deze eenvoudige formules:

zoals besproken, deze formules werken omdat de onderliggende structuur voor onze boom is een Array. Dit verschilt van andere structuren zoals een B-boom, Trie of Grafiek waar men een specifieke aangepaste datastructuur zou toepassen om een model te vertegenwoordigen.

vergelijkingen maken

omdat onze binaire boom eigenlijk niets meer is dan een Array, kunnen we inderdaad basis Enumeratie gebruiken om alle waarden te herhalen. We zullen echter onze formules toepassen om onze kinderbladknopen te bepalen. Eenmaal vastgesteld, kunnen we de totalen van elke sub-boom te volgen met behulp van een eenvoudige vorm van memoization (bijv. dynamische programmering).