Sprawdź, czy drzewo binarne jest symetryczne w Pythonie
Rozwiązałem następujący problem z Leetcode.
Mając drzewo binarne, sprawdź, czy jest swoim zwierciadłem (tj. Symetrycznie wokół swojego środka). Na przykład to drzewo binarne [1,2,2,3,4,4,3] jest symetryczne.
Połączyć: https://leetcode.com/problems/symmetric-tree/
Zrobiłem proste, iteracyjne rozwiązanie, które wymaga \$O(n)\$czas i \$O(n)\$space, ponieważ musimy przeanalizować każdy węzeł, który jest inicjowany jako klasa, a każda klasa zawiera wartości węzła oraz wskaźniki do lewego i prawego dziecka węzła. Porównujemy, czy wartości węzłów na każdym poziomie tworzą listę palindromiczną (przechowujemy wszystkie wartości węzłów w bieżącej liście), czy nie. Tutaj \$n\$oznacza liczbę węzłów w drzewie. Założyłem, że drzewo binarne jest kompletne i każdy brakujący węzeł jest inicjowany za pomocą NONEzmiennej. Kod kończy się, gdy osiągnę poziom w drzewie, na którym każdy węzeł jest a NONE, co oznacza, że nic nie musi być analizowane na tym poziomie i jeśli błąd nie zostanie znaleziony w jednym z poprzednich węzłów (błąd jest zgłaszany, gdy węzły na każdym poziomie nie tworzą listy palindromicznej), zwracamy True.
Uruchomienie kodu w Leetcode zajmuje aż 1500 ms i zajmuje około 150 MB pamięci! Myślę, że około 200 przypadków testowych jest uruchamianych w tle. Uruchomienie kodu na jednym drzewie (o różnych rozmiarach) powoduje, że kod jest uruchamiany w około ~ 30-40 ms.
Powinienem się martwić? Czy są inne istotne sposoby optymalizacji kodu / podejścia? Myślę, że nawet jeśli podejście jest poprawne, implementacja może tracić czas, a ja nie jestem najbardziej doświadczonym programistą. Nie mam doświadczenia w uczeniu się algorytmów i ich implementacji, więc byłbym wdzięczny za opinie.
Edytować:
Oto moja analiza czasu działania algorytmu. Załóżmy, że drzewo jest kompletnym drzewem binarnym, ponieważ każdy brakujący węzeł może być traktowany jako węzeł z NONEprzypisaną do niego klasą. Załóżmy, że drzewo ma \$k\$(zaczynając od poziomu 0) poziomów i łącznie \$n = 2^{k+1} - 1\$węzły. Na przykład drzewo [1|2,2|3,4,4,3], gdzie a |wskazuje na zmianę poziomu, ma \$2\$poziomy z \$ 2^{3} - 1 = 7 \$ węzły.
Zewnętrzna pętla while kończy się, gdy sprawdzimy stan pętli while, gdy osiągniemy poziom \$k + 1\$gdzie ten poziom może być traktowany jako złożony ze wszystkich NONEwęzłów, co oznacza, że drzewo nie rozciąga się aż do tego poziomu. Więc działa tylko wtedy, gdy działająca zmienna \$l\$waha się od \$0\$do \$k\$lub łącznie \$k + 1\$razy, czyli \$\Theta ( \lg (n+1)) = \Theta ( \lg n)\$, gdzie \$\lg\$to logarytm o podstawie 2. W pętli while mamy to dla każdej wartości \$l\$, pierwsza pętla for działa w sumie \$2^{l}\$razy, odkąd każdy poziom ma (najwyżej) \$2^{l}\$węzły. Dodatkowa pętla for działa tylko za \$2\$razy, więc w sumie dla każdej wartości \$l\$są \$O(2^{l})\$iteracje. Wszystkie inne operacje wymagają stałego czasu, więc koszt działania algorytmu wynosi,
$$ \begin{align} O\big(\sum_{l = 0}^{k + 1} 2^{l} \big) &= O\big(\sum_{l = 0}^{\Theta (\lg n)} 2^{l} \big) \\ &= O\big(2^{\Theta (\lg n) + 1 } - 1 \big ) \\ &= O\big(2^{\Theta (\lg n) + 1 } \big) \\ &= O\big(2^{\Theta (\lg n) } \big) \\ &= \Theta (n) \\ &= O(n) \end{align} $$
def isSymmetric(root):
if root == None:
return True
else:
t = [root]
l = 0
d = {None:-1}
while d[None] < 2**l:
d[None] = 0
n = []
v = []
for node in t:
if node == None:
d[None] = d[None] + 2
v.append(None)
v.append(None)
n.append(None)
n.append(None)
else:
for child in [node.left,node.right]:
n.append(child)
if child == None:
d[None] = d[None] + 1
v.append(None)
else:
v.append(child.val)
l = l + 1
if d[None] == 2**l:
return True
else:
a = v[0:2**(l-1)]
b = v[2**(l-1):2**l]
b.reverse()
if a != b:
return False
t = n
Odpowiedzi
Twoje rozwiązanie nie jest \$O(n)\$ale \$O(2^n)\$. Twoje założenie, że drzewo jest kompletne, a zatem Twoja analiza jest niepoprawna. Już drugie przykładowe drzewo LeetCode nie jest kompletne. I rozważ to drzewo:
Że drzewo ma tylko 25 węzłów, ale rozwiązanie tworzy tysiące z Nones do poddrzew, które nie istnieją. (Oznacza to, że rzeczywisty kod przypuszczalnie robi, nie ten, który pisał tutaj i odmawiają fix). Jeśli zrobiłem to dziesięć poziomów głębiej (45 węzły całości), można by stworzyć miliony z Nones.
Przy okazji powyższe drzewo można oznaczyć w LeetCode w ten sposób:
[1,1,1,null,1,1,null,null,1,1,null,null,1,1,null,null,1,1,null,
null,1,1,null,null,1,1,null,null,1,1,null,null,1,1,null,
null,1,1,null,null,1,1,null,null,1,1,null]
Jeszcze jedno rozwiązanie, w którym dostrajam drzewo, a następnie porównuję je z jego lustrzaną wersją. Jest rekurencyjny, co w przypadku problemów z drzewami binarnymi jest często prostsze:
def isSymmetric(self, root: TreeNode) -> bool:
def t(r):
return r and (r.val, t(r.left), t(r.right))
def m(r):
return r and (r[0], m(r[2]), m(r[1]))
r = t(root)
return r == m(r)
Został zaakceptowany w 16 ms. Zwróć uwagę, że skrócone nazwy funkcji / zmiennych są złe w prawdziwym życiu. Ale w przypadku konkursu może to zaoszczędzić czas, więc chciałem to pokazać, ponieważ szybkość pisania została wspomniana w komentarzach w innych miejscach. Podobnie marnuję miejsce na kopię lustrzaną, ponieważ w ten sposób prawie nie muszę myśleć, znowu oszczędzając czas na pisanie :-)
Byłoby też łatwiej, gdybyśmy postępowali zgodnie z TDD - Test Driven Development .
Budujemy płytę kotłową, którą LeetCode buduje dla Ciebie.
from __future__ import annotations import dataclasses from typing import Any, Optional @dataclasses.dataclass class Node: val: Any left: Optional[Node] = None right: Optional[Node] = NoneOtrzymujemy drzewo z działającym tylko jednym węzłem. Dzięki temu możemy rozwinąć testy i kod, aby uzyskać więcej pracy.
Jest to proste, po prostu sprawdzamy, czy lewa i prawa strona to Brak.
def is_symmetric(node): return node.left is None and node.right is None assert is_symmetric(Node(None))Otrzymujemy drzewo z działającymi 3 węzłami.
Najprostszym sposobem jest po prostu sprawdzenie, czy wartości left i right są takie same, ignorując je , czy są one None.
def is_symmetric(node): return ( (node.left is None and node.right is None) or (node.left.val == node.right.val) ) assert is_symmetric(Node(None)) assert is_symmetric(Node(None, Node(1), Node(1))) assert not is_symmetric(Node(None, Node(1), Node(2)))Otrzymujemy drzewo wielkości 1, 2 i 3.
To sprawia, że kod jest nieco bardziej skomplikowany, ponieważ musimy teraz obsłużyć
Noneobaleftiright.def is_symmetric(node): if node.left is None: return node.right is None if node.right is None: return False return node.left.val == node.right.val assert is_symmetric(Node(None)) assert is_symmetric(Node(None, Node(1), Node(1))) assert not is_symmetric(Node(None, Node(1), Node(2))) assert not is_symmetric(Node(None, left=Node(1))) assert not is_symmetric(Node(None, right=Node(1)))Aby łatwiej zrozumieć odskocznię, możemy tymczasowo rozwiązać inny problem. Zamiast sprawdzać, czy jest to lustro wokół katalogu głównego, po prostu sprawdzamy lustro wokół każdego węzła.
Uwaga : ma to na celu tylko ułatwienie przyswojenia tego kroku.
Ponieważ mamy już funkcję sprawdzającą, czy węzeł jest symetryczny, możemy ją po prostu wywołać, aby sprawdzić, czy oba lewe i prawe są symetryczne. Nazywa się to rekurencją.
Aby zwrócić True, prąd
is_symmetricmusi być prawdziwy, a zarówno lewa, jak i prawa strona muszą być symetryczne.Aby nieco ułatwić czytanie kodu, możemy:
- Przenieś bieżący kod do innej funkcji.
- Dodaj warunek, aby zwrócić wartość Prawda, jeśli
nodema wartość Brak.
def _is_symmetric(node): if node.left is None: return node.right is None if node.right is None: return False return node.left.val == node.right.val def is_symmetric(node): if node is None: return True return _is_symmetric(node) and is_symmetric(node.left) and is_symmetric(node.right) assert is_symmetric(Node(None)) assert is_symmetric(Node(None, Node(1), Node(1))) assert not is_symmetric(Node(None, Node(1), Node(2))) assert not is_symmetric(Node(None, left=Node(1))) assert not is_symmetric(Node(None, right=Node(1))) assert is_symmetric(None) assert is_symmetric(Node( None, Node(1, Node(2), Node(2)), Node(1, Node(3), Node(3)), )) assert not is_symmetric(Node( None, Node(1, Node(2), Node(1)), Node(1, Node(3), Node(3)), ))Możemy teraz wrócić do rozwiązywania pierwotnego problemu. Zamieniając dwa węzły wnuków, możemy zmienić powyższe, aby działały na środku drzewa.
def _is_symmetric(node): if node.left is None: return node.right is None if node.right is None: return False return node.left.val == node.right.val def is_symmetric(node): if node is None: return True if not _is_symmetric(node): return False if node.left is not None: (node.left.left, node.right.left) = (node.right.left, node.left.left) return is_symmetric(node.left) and is_symmetric(node.right) assert is_symmetric(Node(None)) assert is_symmetric(Node(None, Node(1), Node(1))) assert not is_symmetric(Node(None, Node(1), Node(2))) assert not is_symmetric(Node(None, left=Node(1))) assert not is_symmetric(Node(None, right=Node(1))) assert is_symmetric(None) assert is_symmetric(Node( None, Node(1, Node(2), Node(3)), Node(1, Node(3), Node(2)), )) assert not is_symmetric(Node( None, Node(1, Node(2), Node(3)), Node(1, Node(3), Node(1)), ))
To działa w \$O(n)\$czas i \$O(d)\$przestrzeń, gdzie \$d\$to głębokość drzewa. To dlatego, że robimy \$d\$stosuj ramki, ponieważ użyliśmy rekurencji. Na całym drzewie \$d\$jest \$\log n\$ale może być tak zły, jak \$n\$ na drzewie bardziej przypominającym linię.
O (1) przestrzeń, O (n) czas
Jak już w pewnym stopniu wskazałem, Twoje listy węzłów / wartości bieżącego poziomu są do \$O(2^n)\$duży. Więc duże zużycie pamięci wynoszące 150 MB nie jest dziwne. Z łatwością mogłoby być znacznie więcej. LeetCode musi mieć tylko bardzo płytkie drzewa (tak właśnie sprawdzone, maksymalna wysokość to tylko 22. Westchnienie). Oto nieco inna skrajność, zajmująca tylko O (1) dodatkowej przestrzeni. I może obsługiwać dowolną wysokość drzewa, w przeciwieństwie do rozwiązań rekurencyjnych, które w pewnym momencie przekroczyłyby limit rekursji i uległy awarii.
Używam przechodzenia Morrisa do przechodzenia od lewej do prawej w przedsprzedaży lewego poddrzewa katalogu głównego i od prawej do lewej z prawego poddrzewa. Podaję nie tylko wartości węzłów, ale także Noneodniesienia. Zapewnia to nie tylko wartości, ale także strukturę dwóch poddrzew, więc po prostu muszę porównać po kolei lewe przejście z prawym przejściem.
W LeetCode nadal zajmuje około 14,3 MB, ponieważ LeetCode nie izoluje wykorzystania pamięci rozwiązania, ale zawiera narzut Python / judge. Wziąłem również rozwiązanie z wykresu dystrybucji pamięci, które miało bardzo niskie zużycie pamięci (13628 kB) i ponownie je przesłałem. Teraz również zajęło 14,3 MB. Podobnie jak w innych czasach, LeetCode nie jest stabilny i dokładny z pamięcią, a linia bazowa (minimum) wydaje się teraz wynosić około 14,3 MB.
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
left = preorder_left_right(root.left)
right = preorder_right_left(root.right)
result = all(map(operator.eq, left, right))
for _ in left: pass
for _ in right: pass
return result
def preorder_left_right(root):
while root:
if not root.left:
yield root.val
yield None
root = root.right
continue
prev = root.left
while prev.right and prev.right is not root:
prev = prev.right
if not prev.right:
yield root.val
prev.right = root
root = root.left
else:
yield None
prev.right = None
root = root.right
yield None
def preorder_right_left(root):
while root:
if not root.right:
yield root.val
yield None
root = root.left
continue
prev = root.right
while prev.left and prev.left is not root:
prev = prev.left
if not prev.left:
yield root.val
prev.left = root
root = root.right
else:
yield None
prev.left = None
root = root.left
yield None
Opróżnianie lefti rightnie jest konieczne w LeetCode, aby zostać zaakceptowanym, również return all(map(operator.eq, left, right))tam działa. Ale robię to, aby zakończyć przemierzanie Morrisa i w ten sposób przywrócić drzewa do ich pierwotnego stanu.
Uważałem zastępując dwie funkcje łączące z jednej funkcji, które zajmuje kid1, kid2i setkid2(uzyskiwanie / ustawianie lewego lub prawego dziecko węzła) w celu usunięcia powielania kodu, ale myślę, że to bardziej przejrzyste tak jest. Edycja: No cóż, właściwie zrobiłem to teraz:
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
left = preorder(root.left, leftkid, rightkid, setright)
right = preorder(root.right, rightkid, leftkid, setleft)
result = all(map(operator.eq, left, right))
for _ in left: pass
for _ in right: pass
return result
def leftkid(node):
return node.left
def rightkid(node):
return node.right
def setleft(node, kid):
node.left = kid
def setright(node, kid):
node.right = kid
def preorder(root, kid1, kid2, setkid2):
while root:
if not kid1(root):
yield root.val
yield None
root = kid2(root)
continue
prev = kid1(root)
while kid2(prev) and kid2(prev) is not root:
prev = kid2(prev)
if not kid2(prev):
yield root.val
setkid2(prev, root)
root = kid1(root)
else:
yield None
setkid2(prev, None)
root = kid2(root)
yield None
Jeszcze inna wersja, wykorzystująca getattri setattr, zainspirowana tą próbą :
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
left = preorder(root.left, 'left', 'right')
right = preorder(root.right, 'right', 'left')
result = all(map(operator.eq, left, right))
for _ in left: pass
for _ in right: pass
return result
def preorder(root, kid1, kid2):
get, set = getattr, setattr
while root:
if not get(root, kid1):
yield root.val
yield None
root = get(root, kid2)
continue
prev = get(root, kid1)
while get(prev, kid2) and get(prev, kid2) is not root:
prev = get(prev, kid2)
if not get(prev, kid2):
yield root.val
set(prev, kid2, root)
root = get(root, kid1)
else:
yield None
set(prev, kid2, None)
root = get(root, kid2)
yield None
Dziękuję wszystkim za sugestie. Byłem w stanie określić błąd w mojej początkowej ocenie i wymyślić rozwiązanie, które działa, a także byłem w stanie je wdrożyć (po kilku czkawkach i drobnych modyfikacjach po drodze). Oto co mam:
def isSymmetric(self,root):
if root == None:
return True
else:
t = [root]
l = 0
while len(t) > 0:
l = l + 1
v = []
n = []
for node in t:
if node.left != None:
n.append(node.left)
v.append(node.left.val)
else:
v.append(None)
if node.right != None:
n.append(node.right)
v.append(node.right.val)
else:
v.append(None)
a = v[::-1]
if a != v:
return False
t = n
return True
Teraz działa w około 26 ms, czyli szybciej niż 96,67% zgłoszeń, ale nadal wykorzystuje około 13 MB pamięci, co stanowi mniej niż 5,09% zgłoszeń. Mogę z tym żyć, ponieważ prawdopodobnie nie jestem najbystrzejszym z programistów, ale spróbuję sprawdzić, czy mogę zoptymalizować i / lub nauczyć się nowych sposobów na lepszą implementację.