Binary Tree Right Side View
Tablica root przechowuje drzewo binarne. Korzeń znajduje się pod indeksem 0, dzieci węzła o indeksie i znajdują się pod indeksami 2*i+1 (lewe) i 2*i+2 (prawe), -1 oznacza puste miejsce, a dodatkowe wpisy -1 mogą występować na końcu.
Spójrz na drzewo z prawej strony. Na każdym poziomie widać dokładnie jeden węzeł — ten położony najbardziej na prawo — który zasłania pozostałe. Wypisz te wartości, zaczynając od poziomu korzenia i schodząc do najgłębszego poziomu.
Funkcja
- rootinteger-array
- drzewo w porządku kopcowym, z -1 oznaczającym puste miejsce
- Zwracainteger-array
- wartość najbardziej po prawej stronie każdego poziomu, zaczynając od najwyższego
Ograniczenia
1 ≤ root.length ≤ 32767- Każde
root[i]ma wartość-1lub wartość spełniającą warunek0 ≤ root[i] ≤ 104. - Wartości węzłów są różne.
root[0]nigdy nie jest równe-1, więc drzewo ma co najmniej jeden węzeł.- Tablica może kończyć się dodatkowymi wpisami
-1za ostatnim węzłem. - Oboje dzieci pustego miejsca również są puste, a drzewo ma najwyżej
14poziomów.
Przykłady
- Wejście
- root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
- Wyjście
- [5, 9, 1, 3]
- Wyjaśnienie
- Po prawej stronie widać
5,9i1(indeks 6). Czwarty poziom zawiera tylko3, na indeksie 8 pod7w lewym poddrzewie. Nic po prawej stronie nie sięga tak głęboko, więc3jest widoczne.
- Wejście
- root = [6, 0, -1, 8, -1, -1, -1]
- Wyjście
- [6, 0, 8]
- Wyjaśnienie
- Drzewo jest łańcuchem lewych dzieci:
6,0,8. Na każdym poziomie znajduje się jeden węzeł, więc widzisz wszystkie trzy, chociaż żaden z nich nie jest prawym dzieckiem.
- Wejście
- root = [42]
- Wyjście
- [42]
- Wyjaśnienie
- Tablica o długości 1: korzeń
42nie ma żadnych miejsc na elementy potomne, a widok zawiera tę jedną wartość.
Pytanie dodatkowe
Jak uzyskać widok drzewa z prawej strony, w którym każdy węzeł może mieć dowolną liczbę dzieci, przechowywanych na liście od lewej do prawej?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Idąc w dół po prawych dzieciach z przykładu 1, otrzymujemy
5, 9, 1i zatrzymujemy się. Odpowiedź zawiera czwartą wartość. Skąd się bierze?Grupuj węzły według głębokości, a nie strony. Zapisz każdy poziom od lewej do prawej: gdzie na tej liście znajduje się węzeł, który zobaczyłaby osoba po prawej stronie?
Prowadź listę
view. Przechodź w głąb, śledząc głębokość, najpierw prawe dziecko, potem lewe, i dodaj węzeł, gdy jego głębokość jest równa długości listyview. Możesz też użyć kolejki, przetwarzając po jednym poziomie w każdej rundzie: dodaj ostatni węzeł z każdej rundy.
Rozwiązanie
Widzisz skrajny prawy węzeł na każdym poziomie i nie musi on być prawym dzieckiem: ostatnia wartość z przykładu 1 znajduje się w lewym poddrzewie. Wyszukiwanie wszerz sprawia, że ten węzeł jest ostatnim w każdej rundzie; przejście w głąb, które najpierw idzie w prawo, napotyka go przed każdym innym węzłem na jego poziomie.
Szerokościowo, ostatni węzeł każdego poziomu
Intuicja
Przetwarzaj drzewo po jednym poziomie na rundę. Gdy rozpoczyna się runda, kolejka zawiera dokładnie jeden poziom, od lewej do prawej, więc ostatni indeks zdjęty z kolejki w tej rundzie odpowiada najbardziej prawemu węzłowi tego poziomu, a jego wartość trafia do wyniku.
W przykładzie 1 rundy to [5], [2, 9], [7, 4, 1] i [3], a ich ostatnie elementy dają 5, 9, 1, 3. Decyduje poziom, a nie strona: 3 znajduje się w lewym poddrzewie, ale jest jedynym węzłem na swoim poziomie.
Każdy indeks jest dodawany do kolejki i zdejmowany z niej raz, więc złożoność czasowa wynosi O(n). Kolejka może urosnąć do szerokości najszerszego poziomu, czyli w najgorszym przypadku do O(n).
Algorytm
- Dodaj indeks korzenia
0do kolejki. - Rozpocznij rundę, zapisując długość kolejki
s. - Usuń z kolejki
sindeksów. Dla każdego indeksuidodaj do kolejki2i+1, a następnie2i+2, jeśli są mniejsze od długości tablicy i nie są równe-1. - Dołącz wartość ostatniego indeksu usuniętego z kolejki w tej rundzie.
- Powtarzaj, aż kolejka będzie pusta, a następnie zwróć odpowiedź.
from collections import deque
def rightSideView(root):
n = len(root)
view = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
size = len(queue) # exactly the nodes of the current level
for j in range(size):
i = queue.popleft()
if j == size - 1:
view.append(root[i]) # the last node of this level
for child in (2 * i + 1, 2 * i + 2):
if child < n and root[child] != -1:
queue.append(child)
return viewW głąb, najpierw prawe dziecko
Intuicja
Przejdź drzewo w głąb, odwiedzając najpierw prawe dziecko, a potem lewe, i przenoś głębokość, zaczynając od 0 w korzeniu. Gdy przejście po raz pierwszy dotrze do głębokości d, odpowiedź zawiera dokładnie d wartości. Wtedy dopisz wartość węzła i pomiń wszystkie kolejne węzły na tym poziomie.
Ten pierwszy węzeł jest najbardziej prawym: wszędzie tam, gdzie dwie ścieżki do poziomu się rozchodzą, przejście podąża prawą gałęzią aż do samego dołu, zanim cofnie się do lewej. W przykładzie 1 przejście odwiedza 5, 9, 1, 2, 4, 7, 3: pomija 2, 4 i 7, których głębokości mają już przypisaną wartość, i dopisuje 3.
Każdy węzeł jest odwiedzany raz, czas działania to O(n), a na stosie znajduje się jedno wywołanie na poziom, maksymalnie 14.
Algorytm
- Zacznij od pustej odpowiedzi, a korzeń umieść na głębokości 0.
- Pomiń indeks, który wykracza poza koniec tablicy lub zawiera
-1. - Gdy długość odpowiedzi jest równa głębokości, dodaj wartość: przejście dotarło do nowego poziomu od prawej strony.
- Najpierw rekurencyjnie przejdź do prawego dziecka
2i+2, a potem do lewego dziecka2i+1, za każdym razem o poziom głębiej. - Zwróć odpowiedź.
def rightSideView(root):
n = len(root)
view = []
def visit(i, depth):
if i >= n or root[i] == -1:
return
if depth == len(view): # the first node met on this level
view.append(root[i])
# Right before left, so the rightmost node of every level comes first.
visit(2 * i + 2, depth + 1)
visit(2 * i + 1, depth + 1)
visit(0, 0)
return view
Pułapki i przypadki brzegowe
- Podążanie od korzenia wyłącznie za prawymi dziećmi. W przykładzie 1 daje to
[5, 9, 1]i pomija3; w przykładzie 2 daje[6]. - Odczytywanie ostatniego miejsca na każdym poziomie,
root[2^(d+1)-2]. W przykładzie 2 indeks 6 zawiera-1; widoczny węzeł8znajduje się pod indeksem 3. - Pominięcie sprawdzania długości w miejscu na dziecko. W przykładzie 1
3jest ostatnim elementem, więc jego miejsca na dzieci o indeksach 17 i 18 nie istnieją. - Dodawanie prawego dziecka do kolejki jako pierwszego i zachowywanie ostatniego węzła z każdej rundy. Zbiera to widok z lewej strony,
[5, 2, 7, 3]. - Pozwalanie późniejszym węzłom nadpisywać wcześniejsze podczas przechodzenia najpierw w prawo, co również daje widok z lewej strony.
Najczęstsze pytania3
Jaka jest złożoność czasowa i pamięciowa problemu widoku prawej strony drzewa binarnego?
Czas wynosi O(n) dla n węzłów i żadne rozwiązanie nie może pomijać węzłów, ponieważ skrajny prawy węzeł na danym poziomie może znajdować się w dowolnym miejscu. Złożoność pamięciowa wynosi O(w) dla kolejki, gdzie w oznacza szerokość najszerszego poziomu, lub O(h) dla przejścia najpierw w prawo po drzewie o h poziomach.
Czy można to rozwiązać za pomocą wyszukiwania w głąb, które najpierw przeszukuje lewą stronę?
Tak, jeśli nadpisujesz wartość zamiast zachowywać pierwszą. Przejście od lewej do prawej odwiedza węzły na każdym poziomie od lewej do prawej, więc zapisuj wartość każdego węzła na jego głębokości i pozwól, by późniejsze węzły zastępowały wcześniejsze. Na końcu na każdej głębokości zostaje wartość najbardziej prawego węzła. Nadal jest to O(n), ale zapis następuje raz na węzeł.
Czy powinienem użyć tutaj przeszukiwania wszerz czy w głąb?
Obie metody są liniowe. Przeszukiwanie wszerz przebiega zgodnie z definicją: jeden poziom na rundę. Przeszukiwanie w głąb zachowuje tylko bieżącą ścieżkę, co oszczędza pamięć w szerokim drzewie, a jego rekurencyjna forma jest krótsza o kilka linijek.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def rightSideView(root):
# Napisz kod tutajTest #1
Test #2
Test #3
Argument
root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
Oczekiwany wynik
[5, 9, 1, 3]