Challenge: vzhledem k * neprázdnému * binárnímu stromu najděte maximální součet cesty. Pro tento problém je cesta definována jako libovolná posloupnost uzlů z nějakého počátečního uzlu do libovolného uzlu ve stromu podél připojení rodič-dítě. Cesta musí obsahovat alespoň jeden uzel a není třeba jít přes root:

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

Příklad #2:

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

Výzva

Jak už název napovídá, binární strom je populární druh stromu-založené datové struktury. Pro podporu jejich časové a prostorové efektivity, stromy jsou často reprezentovány klíčem a dvěma nebo více uzly listů, podobné následujícím strukturám:

As one may guess, recursion is also a common property of tree-based structures. I když většina rekurzivní funkce jsou odsuzovány v reálných aplikacích, stromy umožňují pro určité zefektivnění, jako každý list-uzel může představovat další strom:

pokud nejsou správně pochopeny, stromy mohou vést ke zmatku a přidané složitosti. Vyřešit náš kód výzva, budeme muset vymyslet konzistentní metodu pro navigaci našeho stromu a způsob, jak porovnat všechny možné permutace.

pojďme pracovat vizualizací našich nápadů, než je odevzdáme do kódu. Nejprve se budeme zabývat tím, jak procházet strom. Od stromu-na základě struktury začlenit další pojem vlastnictví *hloubka*, jednoduché techniky, jako je fast-stanovení obsahu nejsou obvykle uplatňovány. Místo toho můžeme použít specifické traversální algoritmy, jako je hloubka nebo šířka vyhledávání (např. I když téma BFS je dostatečně podrobné, aby pro nové diskuse, můžeme uzavřít, to by bylo normální, jak by traverse takové struktury. Protože však pracujeme s binárním stromem, můžeme použít specifické algoritmické efektivity, které pomohou zkrátit proces procházení.

Co je tedy binární strom? V podstatě je to standardní pole, které je vizualizováno jako strom. V tomto případě je kladen důraz na vizualizační aspekty, protože to ovlivní způsob navigace ve struktuře. Například pro každý uzel lze jeho podřízené uzly levého a pravého listu vypočítat pomocí těchto jednoduchých vzorců:

Jak bylo uvedeno, tyto vzorce fungují, protože základní struktura našeho stromu je pole. To se liší od jiných struktur, jako je B-strom, Trie nebo graf, kde by člověk použil specifickou vlastní datovou strukturu k reprezentaci modelu.

porovnávání

protože náš binární strom není ve skutečnosti nic jiného než pole, můžeme skutečně použít základní výčet k iteraci všech hodnot. Použijeme však naše vzorce k určení uzlů dětských listů. Po založení můžeme sledovat součty každého substromu pomocí jednoduché formy memoizace (např. dynamické programování).