Maximum Depth of Binary Tree

Q: Jaka jest złożoność czasowa algorytmu wyznaczającego maksymalną głębokość 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 bieżącą ś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 obejmuje około połowy węzłów.

Q: Czy do wyznaczenia maksymalnej głębokości drzewa binarnego należy użyć DFS czy BFS?

Oba działają w czasie O(n) . Przeszukiwanie w głąb jest krótsze do zapisania i zużywa pamięć proporcjonalnie do głębokości, dlatego sprawdza się w szerokich, płytkich drzewach. Przeszukiwanie wszerz bezpośrednio zlicza poziomy i zużywa pamięć proporcjonalnie do najszerszego poziomu, dlatego sprawdza się w głębokich, wąskich drzewach. Przy szukaniu minimalnej głębokości wygrywa BFS, ponieważ może zakończyć działanie po dotarciu do pierwszego liścia.

Q: Jaka jest różnica między głębokością a wysokością drzewa binarnego?

Głębokość węzła określa liczbę kroków od korzenia do tego węzła; wysokość określa liczbę kroków od niego do jego najgłębiej położonego liścia. Maksymalna głębokość drzewa jest równa wysokości korzenia. W tym zadaniu liczone są węzły, więc pojedynczy węzeł ma głębokość 1 ; licząc krawędzie, otrzymujemy o jeden mniej.

ŁatwePrzechodzenie drzewa

+10

Otrzymujesz drzewo binarne przechowywane 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

maxDepth(tree: integer-array) → integer

treeinteger-array: drzewo binarne w kolejności 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żdy element tree[i] ma wartość -1 lub wartość z zakresu 0 ≤ 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 -1 za ostatnim węzłem.
Oba dzieci puste 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 (indeksy 0, 1, 4, 9), która zawiera 4 węzły. Ścieżka przez 1 kończy się po 2 węzłach.

Wejście: tree = [7, -1, -1]
Wyjście: 1
Wyjaśnienie: Dwa wpisy -1 to puste miejsca na dzieci korzenia. Sam korzeń stanowi ścieżkę składającą się z jednego węzła, więc głębokość wynosi 1, a nie 0.

Wejście: tree = [2, -1, 9, -1, -1, -1, 4]
Wyjście: 3
Wyjaśnienie: Korzeń 2 nie ma lewego dziecka. Jego prawe dziecko 9 o indeksie 2 ma 4 o indeksie 6 jako prawe dziecko — ścieżka składająca się z 3 węzłów.

Pytanie dodatkowe

Jak zwrócić wartości z najdłuższej ścieżki od korzenia do liścia, a także jej długość? Jeśli kilka ścieżek ma tę samą długość, którą z nich zwrócisz?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Głębokość jest wyznaczana przez najdłuższą gałąź i nie da się ustalić, która to gałąź, bez odwiedzenia każdego węzła. Dlatego potrzebujesz jednego pełnego przejścia, które na każdym węźle zna jego głębokość. Rekurencja, przeszukiwanie wszerz poziomami oraz przeszukiwanie w głąb z własnym stosem wykonują to w jednym przebiegu.

Rekurencja w dwóch poddrzewach

Intuicja

Pozycja potomka jest rzeczywista, gdy jej indeks znajduje się w tablicy, a jej wartość nie jest równa -1. Najgłębsza ścieżka przechodząca przez węzeł schodzi w głąb jego poddrzewa, więc głębokość na indeksie i wynosi 1 dla węzła plus większa z głębokości na indeksach 2*i+1 i 2*i+2. Pusta pozycja ma głębokość 0, co kończy rekurencję. Liść otrzymuje 1 + max(0, 0) = 1, a wartości wracają w górę do korzenia.

Każdy węzeł jest odwiedzany raz. Stos wywołań przechowuje po jednej ramce na każdy poziom bieżącej ścieżki, O(h), tutaj najwyżej 14.

Algorytm

Napisz depth(i): jeśli i wykracza poza koniec tablicy lub tree[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, więc możesz liczyć poziomy zamiast podążać ścieżkami. Kolejka odwiedza węzły w kolejności poziomów. Przed każdą partią odczytaj rozmiar kolejki: te węzły znajdują się dokładnie na jednym poziomie, ponieważ dzieci dodane w trakcie partii trafiają za nimi. Każda partia zwiększa głębokość o 1. W pierwszym przykładzie partie to [5], [8, 1], [3] i [6], więc odpowiedź wynosi 4.

Kolejka przechowuje jednocześnie jeden poziom, czyli O(w) dla najszerszego poziomu. W pełnym drzewie o głębokości 14 jest to 8192 z 16383 węzłów.

Algorytm

Umieść indeks korzenia 0 w kolejce i ustaw depth = 0.
Gdy kolejka nie jest pusta, dodaj 1 do depth i odczytaj rozmiar kolejki.
Wyjmij tyle indeksów. Dla każdego z nich dodaj do kolejki indeksy potomków 2*i+1 i 2*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 depth

Przeszukiwanie w głąb z jawnym stosem

Intuicja

Utwórz własny stos par: indeks węzła i jego głębokość, ponieważ nic innego nie pamięta, jak głęboko znajduje się węzeł. Zacznij od (0, 1), czyli korzenia na głębokości 1. Każdy węzeł jest dodawany na stos raz, wraz z długością ścieżki, która do niego prowadzi, więc największa głębokość zdjętego węzła jest odpowiedzią. W pierwszym przykładzie 6 jest dodawane na stos jako (9, 4).

Stos przechowuje około jednego oczekującego rodzeństwa na poziom, O(h), bez stosu wywołań, który mógłby się przepełnić. Ten sam kod działa na drzewie opartym na wskaźnikach o dowolnej głębokości.

Algorytm

Umieść (0, 1) na stosie i ustaw best = 0.
Zdejmij parę (i, depth) ze stosu i ustaw best na większą z wartości best i depth.
Dla każdego indeksu dziecka 2*i+1 i 2*i+2, który znajduje się w tablicy i nie jest równy -1, umieść go na stosie z wartością depth + 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

Liczenie krawędzi zamiast węzłów. [7, -1, -1] ma głębokość 1, a nie 0.
Pominięcie sprawdzania granic. W pierwszym przykładzie 6 na indeksie 9 ma indeksy dzieci 19 i 20, które wykraczają poza koniec tablicy. Przed odczytaniem tree[child] sprawdź child < n.
Obliczanie głębokości na podstawie długości tablicy. Końcowe wpisy -1 sięgają poziomu bez węzła: [7, -1, -1] ma długość 3, ale głębokość 1.
Odczytywanie rozmiaru kolejki wewnątrz pętli przetwarzającej partię. Dzieci dodane podczas przetwarzania partii zmieniają ten rozmiar, więc najpierw go zapisz.
Pomylenie przesunięcia w Lua i R, gdzie tablice zaczynają się od 1. Zachowaj indeksy węzłów liczone od 0 dla 2*i+1 i odczytuj tree[i + 1].

Najczęstsze pytania3

Jaka jest złożoność czasowa algorytmu wyznaczającego maksymalną głębokość 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 bieżącą ś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 obejmuje około połowy węzłów.

Czy do wyznaczenia maksymalnej głębokości drzewa binarnego należy użyć DFS czy BFS?

Oba działają w czasie O(n). Przeszukiwanie w głąb jest krótsze do zapisania i zużywa pamięć proporcjonalnie do głębokości, dlatego sprawdza się w szerokich, płytkich drzewach. Przeszukiwanie wszerz bezpośrednio zlicza poziomy i zużywa pamięć proporcjonalnie do najszerszego poziomu, dlatego sprawdza się w głębokich, wąskich drzewach. Przy szukaniu minimalnej głębokości wygrywa BFS, ponieważ może zakończyć działanie po dotarciu do pierwszego liścia.

Jaka jest różnica między głębokością a wysokością drzewa binarnego?

Głębokość węzła określa liczbę kroków od korzenia do tego węzła; wysokość określa liczbę kroków od niego do jego najgłębiej położonego liścia. Maksymalna głębokość drzewa jest równa wysokości korzenia. W tym zadaniu liczone są węzły, więc pojedynczy węzeł ma głębokość 1; licząc krawędzie, otrzymujemy o jeden mniej.

def maxDepth(tree):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argument

tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]

Oczekiwany wynik

Maximum Depth of Binary Tree

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Rekurencja w dwóch poddrzewach

Przeszukiwanie wszerz, poziom po poziomie

Przeszukiwanie w głąb z jawnym stosem

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania