Challenge: biorąc pod uwagę *niepuste* drzewo binarne, znajdź maksymalną sumę ścieżek. W przypadku tego problemu ścieżka jest definiowana jako dowolna Sekwencja węzłów od jakiegoś węzła początkowego do dowolnego węzła w drzewie wzdłuż połączeń rodzic-dziecko. Ścieżka musi zawierać co najmniej jeden węzeł i nie musi przechodzić przez główny:

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

przykład #2:

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

wyzwanie

jak sama nazwa wskazuje, drzewo binarne jest popularnym typem drzewiastej struktury danych. Aby wspomóc ich efektywność czasową i przestrzenną, drzewa są często reprezentowane przez klucz i dwa lub więcej węzłów liści, podobne do następujących struktur:

As one may guess, recursion is also a common property of tree-based structures. Chociaż większość funkcji rekurencyjnych jest źle widziana w rzeczywistych aplikacjach, drzewa pozwalają na pewne wydajności, ponieważ każdy węzeł liści może również reprezentować inne drzewo:

Jeśli nie jest poprawnie zrozumiany, drzewa mogą prowadzić do zamieszania, a także do dodatkowej złożoności. Aby rozwiązać nasze wyzwanie dotyczące kodu, musimy opracować spójną metodę nawigacji po drzewie i sposób porównywania wszystkich możliwych permutacji.

popracujmy nad wizualizacją naszych pomysłów przed zatwierdzeniem ich do kodu. Na początek zajmiemy się najpierw poruszaniem się po drzewie. Ponieważ struktury oparte na drzewie zawierają dodatkową właściwość *depth*, proste techniki, takie jak szybkie wyliczanie, nie są zwykle stosowane. Zamiast tego możemy użyć specyficznych algorytmów przeszukiwania, takich jak wyszukiwanie wgłębne lub szerokie (np. odpowiednio DFS i BFS). Chociaż temat BFS jest wystarczająco szczegółowy do nowej dyskusji, możemy stwierdzić, że byłby to normalny sposób, w jaki można by przemierzyć taką strukturę. Ponieważ jednak pracujemy z drzewem binarnym, możemy zastosować określone algorytmiczne usprawnienia, aby skrócić proces przechodzenia.

Co To jest drzewo binarne? Zasadniczo jest to standardowa tablica, która jest wizualizowana jako drzewo. W tym przypadku nacisk kładzie się na aspekty wizualizacji, ponieważ wpłynie to na sposób poruszania się po strukturze. Na przykład, dla każdego węzła, jego lewy i prawy węzeł potomny może być obliczony przy użyciu tych prostych formuł:

jak omówiono, formuły te działają, ponieważ podstawową strukturą naszego drzewa jest tablica. Różni się to od innych struktur, takich jak B-tree, Trie lub Graph, gdzie można zastosować określoną niestandardową strukturę danych do reprezentowania modelu.

dokonywanie porównań

ponieważ nasze drzewo binarne jest niczym więcej niż tablicą, możemy rzeczywiście użyć podstawowego wyliczenia do iteracji wszystkich wartości. Jednak zastosujemy nasze formuły, aby określić węzły liści potomnych. Po ustaleniu, możemy śledzić sumy każdego sub-drzewa za pomocą prostej formy memoizacji(np. programowanie dynamiczne).