Maximum Depth of Binary Tree
Otrzymujesz drzewo binarne zapisane w tablicy tree w kolejności poziomami. Korzeń znajduje się pod indeksem 0, dzieci węzła pod indeksem i znajdują się pod indeksami 2*i+1 (lewe) i 2*i+2 (prawe), -1 oznacza puste miejsce, a tablica może kończyć się dodatkowymi wpisami -1. Zwróć maksymalną głębokość drzewa: liczbę węzłów na najdłuższej ścieżce od korzenia do liścia.
Funkcja
- treeinteger-array
- drzewo binarne w porządku poziomami, z wartością -1 oznaczającą puste miejsce
- Zwracainteger
- liczba węzłów na najdłuższej ścieżce od korzenia do liścia
Ograniczenia
1 ≤ tree.length ≤ 32767- Każde
tree[i]jest równe-1lub ma wartość spełniającą warunek0 ≤ tree[i] ≤ 1000. tree[0]nigdy nie jest równe-1, więc drzewo ma co najmniej jeden węzeł.- Tablica może kończyć się dodatkowymi wpisami
-1po ostatnim węźle. - Oba węzły potomne pustego miejsca również są puste, a głębokość wynosi co najwyżej
14.
Przykłady
- Wejście
- tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
- Wyjście
- 4
- Wyjaśnienie
- Najdłuższa ścieżka to
5,8,3,6(indeksy0,1,4,9), która zawiera 4 węzły. Ścieżka przez1kończy się po 2 węzłach.
- Wejście
- tree = [7, -1, -1]
- Wyjście
- 1
- Wyjaśnienie
- Dwa wpisy
-1oznaczają puste miejsca na dzieci korzenia. Sam korzeń stanowi ścieżkę złożoną z jednego węzła, więc głębokość wynosi1, a nie0.
- Wejście
- tree = [2, -1, 9, -1, -1, -1, 4]
- Wyjście
- 3
- Wyjaśnienie
- Korzeń
2nie ma lewego dziecka. Jego prawe dziecko9pod indeksem2ma4pod indeksem6jako prawe dziecko, co daje ścieżkę z 3 węzłów.
+13 ukrytych testów przy wysłaniu
Pytanie dodatkowe
Jak zwrócisz wartości z najdłuższej ścieżki od korzenia do liścia, a nie tylko jej długość? Jeśli kilka ścieżek ma taką samą długość, którą z nich zwrócisz i jak określisz to w kontrakcie?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Pomyśl o korzeniu. Gdybyś znał głębokość jego lewego poddrzewa i głębokość prawego poddrzewa, jaka byłaby głębokość całego drzewa?
To
1dla korzenia plus większa z głębokości dwóch poddrzew, a puste miejsce ma głębokość0. Ta sama zasada obowiązuje w każdym węźle, więc przejście, które zna głębokość każdego węzła, może znaleźć odpowiedź.Przechowuj stos par: indeks węzła i jego głębokość, zaczynając od korzenia na głębokości 1. Zdejmij parę ze stosu, zapamiętaj największą dotychczasową głębokość i dodaj każde dziecko o indeksie
2*i+1i2*i+2, które mieści się w tablicy i nie ma wartości-1, z głębokością większą o jeden.
Rozwiązanie
Głębokość wyznacza pojedyncza najdłuższa gałąź, a nie da się stwierdzić, która to gałąź, bez sprawdzenia każdego węzła. Dlatego zadanie wymaga pełnego przejścia, które śledzi głębokość w każdym węźle. Rekurencja, wyszukiwanie wszerz poziom po poziomie oraz wyszukiwanie w głąb z użyciem własnego stosu wykonują je w jednym przebiegu; różnią się sposobem śledzenia aktualnego położenia.
Rekurencja w dwóch poddrzewach
Intuicja
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. Dziecko istnieje tylko wtedy, gdy jego indeks znajduje się w tablicy, a wartość pod tym indeksem nie jest równa -1. W tablicy [5, 8, 1, -1, 3, -1, -1, -1, -1, 6] korzeń 5 ma dzieci pod indeksami 1 i 2, węzeł 8 pod indeksem 1 ma puste miejsce po lewej stronie pod indeksem 3 i węzeł 3 pod indeksem 4 po prawej stronie, a węzeł 3 ma poniżej siebie węzeł 6 pod indeksem 9.
Teraz sama idea. Najgłębsza ścieżka przechodząca przez węzeł prowadzi w dół do głębszego z jego dwóch poddrzew. Głębokość poddrzewa pod indeksem i to 1 dla samego węzła plus większa z głębokości pod indeksami 2*i+1 i 2*i+2. Puste miejsce ma głębokość 0, co kończy rekurencję. Liść otrzymuje wartość 1 + max(0, 0) = 1, a wartości wspinają się z powrotem do korzenia.
Każdy węzeł jest odwiedzany raz, więc złożoność czasowa wynosi O(n). Stos wywołań przechowuje jedną ramkę na każdy poziom bieżącej ścieżki, czyli O(h), gdzie h to głębokość, tutaj najwyżej 14. To ograniczenie sprawia, że rekurencja jest bezpieczna w tym zadaniu. W drzewie opartym na wskaźnikach i ukształtowanym jak długa lista ten sam kod osiągnąłby limit rekurencji, który w Pythonie wynosi 1000 ramek.
Algorytm
- Napisz
depth(i): jeśliiwykracza poza koniec tablicy lubtree[i]ma wartość-1, zwróć0. - W przeciwnym razie zwróć
1 + max(depth(2*i+1), depth(2*i+2)). - Zwróć
depth(0).
def maxDepth(tree):
def depth(i):
# An index past the end or a -1 is an empty spot: depth 0.
if i >= len(tree) or tree[i] == -1:
return 0
return 1 + max(depth(2 * i + 1), depth(2 * i + 2))
return depth(0)Przeszukiwanie wszerz, poziom po poziomie
Intuicja
Maksymalna głębokość to liczba poziomów w drzewie, więc możesz liczyć poziomy zamiast podążać ścieżkami. Kolejka odwiedza węzły w kolejności poziomami: zacznij od korzenia, a za każdym razem, gdy wyjmujesz węzeł, dodaj jego rzeczywiste dzieci na koniec kolejki.
Aby policzyć poziomy, przetwarzaj kolejkę partiami. Przed każdą partią sprawdź, ile węzłów zawiera kolejka. Są to dokładnie węzły jednego poziomu, ponieważ dzieci dodawane podczas przetwarzania partii trafiają za nimi. Wyjmij tyle węzłów, dodaj ich dzieci do kolejki i zwiększ głębokość o 1. Gdy kolejka będzie pusta, głębokość będzie równa liczbie partii. W pierwszym przykładzie partie to [5], [8, 1], [3] i [6], więc odpowiedź to 4.
Każdy węzeł trafia do kolejki i jest z niej usuwany raz, co daje czas O(n). Kolejka przechowuje naraz węzły jednego poziomu, więc złożoność pamięciowa wynosi O(w) dla najszerszego poziomu w. W pełnym drzewie najniższy poziom zawiera około połowy węzłów: 8192 z 16383 na głębokości 14.
Algorytm
- Umieść indeks korzenia
0w kolejce i ustawdepth = 0. - Gdy kolejka nie jest pusta, dodaj
1dodepthi odczytaj rozmiar kolejki. - Wyjmij tyle indeksów. Dla każdego dodaj do kolejki indeksy dzieci
2*i+1i2*i+2, które mieszczą się w tablicy i nie są równe-1. - Gdy kolejka będzie pusta, zwróć
depth.
from collections import deque
def maxDepth(tree):
n = len(tree)
queue = deque([0])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)): # exactly the nodes of this level
i = queue.popleft()
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
queue.append(child)
return depthPrzeszukiwanie w głąb z jawnym stosem
Intuicja
Możesz przechodzić ścieżki tak jak rekurencja, nie wykonując ani jednego wywołania rekurencyjnego. Użyj własnego stosu i zapisuj każdy węzeł wraz z jego głębokością, ponieważ nic innego nie pamięta, jak daleko w dół się znajduje. Zacznij od pary (0, 1): korzenia na głębokości 1.
Zdejmij parę ze stosu, porównaj jej głębokość z największą dotąd napotkaną i dodaj każde istniejące dziecko wraz z wartością depth + 1. Każdy węzeł drzewa jest dodawany dokładnie raz, wraz z długością ścieżki, która do niego prowadzi, więc największa głębokość zdjętej pary jest odpowiedzią. W pierwszym przykładzie wartość 6 o indeksie 9 zostaje dodana jako (9, 4), a żadna para nie schodzi głębiej.
Złożoność czasowa wynosi O(n). Stos przechowuje oczekujące rodzeństwo węzłów na bieżącej ścieżce, najwyżej mniej więcej po jednym na poziom, więc złożoność pamięciowa wynosi O(h) — tyle samo co w przypadku rekurencji, ale bez ryzyka przepełnienia stosu wywołań. Po tę wersję warto sięgnąć, gdy drzewo może być głębokie; można ją też bez zmian zastosować do drzew opartych na wskaźnikach.
Algorytm
- Umieść
(0, 1)na stosie i ustawbest = 0. - Zdejmij parę
(i, depth)ze stosu i ustawbestna większą z wartościbestidepth. - Dla każdego indeksu dziecka
2*i+1i2*i+2, który znajduje się w tablicy i nie ma wartości-1, umieść go na stosie razem zdepth + 1. - Powtarzaj, aż stos będzie pusty, a następnie zwróć
best.
def maxDepth(tree):
n = len(tree)
best = 0
stack = [(0, 1)] # (node index, depth of that node); the root is never empty
while stack:
i, depth = stack.pop()
best = max(best, depth)
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
stack.append((child, depth + 1))
return best
Pułapki i przypadki brzegowe
Większość błędnych odpowiedzi w tym zadaniu wynika z pomyłki o jeden albo z traktowania pustego miejsca jak węzła.
- Liczenie krawędzi zamiast węzłów. Pojedynczy węzeł ma tu głębokość
1; zwrócenie dla niego0albo3dla ścieżki z 4 węzłów oznacza wynik mniejszy o jeden. - Pominięcie sprawdzenia zakresu. Liść znajdujący się blisko końca tablicy może mieć indeksy dzieci wykraczające poza jej ostatni element, ponieważ tablica może kończyć się zaraz za ostatnim węzłem. Sprawdź
child < nprzed odczytaniemtree[child]. - Odczytywanie głębokości z długości tablicy. Na końcu tablicy mogą znajdować się dodatkowe elementy
-1, więc jej długość może odpowiadać poziomowi głębszemu niż poziom dowolnego rzeczywistego węzła. - Traktowanie
-1jak wartości. Oznacza brak węzła, więc nie wolno go dodawać na stos, do kolejki ani uwzględniać w obliczeniach. - Zakładanie, że drzewo jest zrównoważone. Odpowiedź zależy od najdłuższej gałęzi, na przykład lewego łańcucha z 14 węzłami, w którym każde prawe miejsce jest puste.
- Odczytywanie rozmiaru kolejki wewnątrz pętli w wersji przeszukiwania wszerz. Rozmiar zmienia się podczas dodawania dzieci, więc zapisz go przed rozpoczęciem przetwarzania danej partii.
- Pomylenie przesunięcia w Lua i R, gdzie indeksowanie tablic zaczyna się od 1. Zachowaj indeksy węzłów liczone od 0 na potrzeby obliczenia
2*i+1i odczytujtree[i + 1].
Najczęstsze pytania4
Jaka jest złożoność czasowa problemu maksymalnej głębokości drzewa binarnego?
Każde podejście odwiedza każdy węzeł raz, więc złożoność czasowa wynosi O(n). Wersje przeszukiwania w głąb używają O(h) dodatkowej pamięci na badaną ścieżkę, gdzie h to głębokość. Wersja przeszukiwania wszerz używa O(w) pamięci dla najszerszego poziomu, który w pełnym drzewie może obejmować około połowy węzłów.
Czy do wyznaczenia maksymalnej głębokości drzewa binarnego należy użyć DFS czy BFS?
Oba algorytmy znajdują prawidłową odpowiedź w czasie O(n). Wyszukiwanie w głąb jest krótsze do zapisania i zużywa pamięć proporcjonalnie do głębokości, dlatego sprawdza się w przypadku szerokich, płytkich drzew. Wyszukiwanie wszerz bezpośrednio zlicza poziomy i zużywa pamięć proporcjonalnie do najszerszego poziomu, dlatego sprawdza się w przypadku głębokich, wąskich drzew. Przy szukaniu minimalnej głębokości BFS ma przewagę, ponieważ może zakończyć działanie po napotkaniu pierwszego liścia.
Jak znaleźć maksymalną głębokość drzewa binarnego bez użycia rekurencji?
Użyj jawnego stosu par: węzła i jego głębokości. Zacznij od korzenia na głębokości 1, zdejmij parę ze stosu, zapisz jej głębokość i dodaj każde dziecko z głębokością większą o jeden. Największa głębokość zdjęta ze stosu jest odpowiedzią. Działa też kolejka przetwarzana poziom po poziomie, zliczająca po jednym poziomie.
Jaka jest różnica między głębokością a wysokością drzewa binarnego?
Głębokość węzła oznacza liczbę kroków od korzenia do tego węzła, a wysokość węzła — liczbę kroków od niego do jego najgłębszego liścia. Maksymalna głębokość drzewa i wysokość korzenia są takie same. W tym zadaniu liczone są węzły, więc pojedynczy węzeł ma głębokość 1; niektóre książki liczą zamiast tego krawędzie, co daje wynik mniejszy o jeden.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
Python
def maxDepth(tree):
# Wpisz kod tutajPrzypadek 1
Przypadek 2
Przypadek 3
Wejście
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Oczekiwane
4