Algorytm wyszukiwania głębokości w celu sprawdzenia, czy dwa drzewa wyrażeń są równoważne

Drzewo wyrażeń binarnych to rodzaj drzewa binarnego używanego do reprezentowania wyrażeń arytmetycznych. Każdy węzeł drzewa wyrażeń binarnych ma zero lub dwoje dzieci. Węzły liścia (węzły z 0 dziećmi) odpowiadają operandom (zmiennym), a węzły wewnętrzne (węzły z dwójką dzieci) odpowiadają operatorom. W tym problemie bierzemy pod uwagę tylko operator „+" (tj. dodawanie).

wyrażenie-drzewo-binarne

Otrzymasz korzenie dwóch binarnych drzew wyrażeń, root1 i root2. Zwróć wartość true, jeśli dwa drzewa wyrażeń binarnych są równoważne. W przeciwnym razie zwróć fałsz.

Dwa drzewa wyrażeń binarnych są równoważne, jeśli mają taką samą wartość, niezależnie od tego, jak ustawione są zmienne.

Kontynuacja: Co zmienisz w swoim rozwiązaniu, jeśli drzewo obsługuje również operator „-” (tj. odejmowanie)?

Przykład 1:
Wejście: root1 = [x], root2 = [x]
Wyjście: prawda

Przykład 2:
Dane wejściowe: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a] Dane
wyjściowe: true
Wyjaśnienie: a + (b + c) == (b + c) + a

Przykład 3:
Wejście: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
Wyjście: false
Wyjaśnienie: a + (b + c) != (b + d) + a

Ograniczenia:
Liczba węzłów w obu drzewach jest równa, nieparzysta i mieści się w przedziale [1, 4999].
Node.val to „+” lub mała litera angielska.
Gwarantujemy, że podane drzewo jest prawidłowym drzewem wyrażeń binarnych.

Wskazówki:
Policz dla każdej zmiennej ile razy pojawiła się w pierwszym drzewie.
Zrób to samo dla drugiego drzewa i sprawdź, czy liczba jest taka sama dla obu drzew.

Algorytm pierwszego wyszukiwania głębokości z tablicą mieszającą

Ponieważ drzewo wyrażeń jest binarne i może zawierać tylko jeden symbol plusa. Dlatego możemy wykonać algorytm pierwszego wyszukiwania głębokości (DFS) na obu drzewach wyrażeń binarnych i policzyć każdą zmienną. Dwa drzewa wyrażeń są równe, jeśli oba drzewa zawierają taką samą liczbę zmiennych.

System plików DFS działa w czasie O(N), gdzie N jest liczbą węzłów w obu drzewach wyrażeń binarnych. Złożoność przestrzeni wynosi O(N), ponieważ używamy stosu za pomocą rekurencji, a także musimy rejestrować liczniki dla każdej zmiennej.

Aby porównać, czy dwa hash map są równe (unordered_map ), możemy je po prostu porównać w C++ za pomocą podwójnego znaku równości.