Diameter of Binary Tree

Najpierw: jak poruszać się po tablicy. Węzeł o indeksie i ma lewe dziecko pod indeksem 2*i+1, a prawe dziecko pod indeksem 2*i+2, więc jego rodzic znajduje się pod indeksem (i-1)/2, zaokrąglonym w dół. Miejsce jest rzeczywiste tylko wtedy, gdy jego indeks mieści się w tablicy, a jego wartość nie jest równa -1. W [8, 3, 6, 1, 4, -1, -1, -1, -1, 7] węzeł 7 o indeksie 9 ma rodzica pod indeksem 4, a ten 4 ma rodzica pod indeksem 1.

Średnica to największa odległość między dwoma węzłami, więc możesz zmierzyć każdą parę. Aby obliczyć odległość między indeksami a i b, wspinaj się w stronę korzenia krok po kroku, aż się spotkają, za każdym razem zaczynając od większego indeksu. Większy indeks nigdy nie znajduje się na wyższym poziomie, więc ten krok nigdy nie minie miejsca spotkania. Liczba kroków to liczba krawędzi. Dla 9 i 2: 9 wspina się do 4, a potem do 1, 2 wspina się do 0, a 1 wspina się do 0. Cztery kroki.

To rozwiązanie jest poprawne, ale powolne. Największy test to pełne drzewo o 16383 węzłach, co daje około 1.3 × 10^8 par, a każda para wymaga do 26 kroków. Miliardy kroków dla jednej odpowiedzi to znacznie więcej, niż pozwala limit czasu.

Przyjrzyj się najdłuższej ścieżce od jej najwyższego węzła — tego, w którym przestaje ona prowadzić w górę i zaczyna prowadzić w dół. Stamtąd prowadzi ona jak najniżej lewą stroną i jak najniżej prawą stroną. Niech height(c) zlicza węzły na najdłuższej ścieżce w dół od c, przyjmując 0 dla pustego miejsca. Wtedy najdłuższa ścieżka skręcająca w węźle i ma height(2*i+1) + height(2*i+2) krawędzi, po jednej krawędzi dla każdego z tych węzłów.

Wypróbuj więc każdy węzeł jako punkt skrętu i zachowaj najlepszy wynik. W drugim przykładzie 5 o indeksie 1 ma wysokość 2 po lewej stronie (1, 3) i 2 po prawej stronie (9, 4), co daje ścieżkę o długości czterech krawędzi. Korzeń ma wysokość 3 po lewej stronie i 0 po prawej, co daje tylko trzy krawędzie.

Każde wywołanie height przechodzi przez całe poddrzewo, a do węzła wraca się ponownie dla każdego jego przodka, więc złożoność wynosi O(n·h). Przy h ≤ 14 to wystarczająco szybkie rozwiązanie, ale w drzewie wskaźnikowym o kształcie łańcucha h może osiągnąć n, a wtedy ta sama metoda ma złożoność O(n²). Powtarzające się wywołania height to zbędna praca, którą eliminuje ostatnie podejście.

Wysokość węzła zależy tylko od wysokości jego dwojga dzieci, a to właśnie te same dwie liczby są potrzebne do sprawdzenia punktu zwrotnego. Oblicz je więc raz, od dołu do góry. Przejście w porządku post-order kończy przetwarzanie obojga dzieci, zanim przetworzy ich rodzica. W każdym węźle masz wtedy left i right: zaktualizuj wynik, używając left + right, a rodzicowi przekaż 1 + max(left, right).

W pierwszym przykładzie liść 7 zwraca 1, znajdujący się nad nim węzeł 4 zwraca 2, a węzeł 3 zwraca 3, ponieważ jego drugie dziecko 1 ma wysokość 1. Węzeł 6 zwraca 1. W korzeniu left + right = 3 + 1 = 4 — to jest wynik. Najlepszy wynik, jaki może dać dowolny inny węzeł, to 3, przy 1 + 2 = 3.

Każdy węzeł jest odwiedzany raz, więc czas działania wynosi O(n), a rekurencja sięga tak głęboko jak drzewo: O(h), czyli około jednej ramki na poziom. Wynik jest przechowywany w zmiennej poza rekurencją, ponieważ to, co zwraca wywołanie (wysokość), różni się od tego, czego potrzebujesz na końcu (długości ścieżki).