Tiefensuchalgorithmus zum Prüfen, ob zwei Ausdrucksbäume äquivalent sind

Ein binärer Ausdrucksbaum ist eine Art binärer Baum, der verwendet wird, um arithmetische Ausdrücke darzustellen. Jeder Knoten eines binären Ausdrucksbaums hat entweder null oder zwei Kinder. Blattknoten (Knoten mit 0 Kindern) entsprechen Operanden (Variablen) und interne Knoten (Knoten mit zwei Kindern) entsprechen den Operatoren. Bei diesem Problem betrachten wir nur den ‘+’-Operator (dh Addition).

Ausdruck-Binärbaum

Sie erhalten die Wurzeln von zwei binären Ausdrucksbäumen, root1 und root2. Geben Sie true zurück, wenn die beiden binären Ausdrucksbäume äquivalent sind. Geben Sie andernfalls false zurück.

Zwei binäre Ausdrucksbäume sind äquivalent, wenn sie denselben Wert ergeben, unabhängig davon, auf was die Variablen eingestellt sind.

Follow-up: Was werden Sie in Ihrer Lösung ändern, wenn der Baum auch den ‘-‘-Operator (dh Subtraktion) unterstützt?

Beispiel 1:
Eingabe: Wurzel1 = [x], Wurzel2 = [x]
Ausgabe: wahr

Beispiel 2:
Eingabe: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
Ausgabe: true
Erklärung: a + (b + c) == (b+c)+a

Beispiel 3:
Eingabe: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
Ausgabe: false
Erklärung: a + (b + c) != (b+d)+a

Einschränkungen:
Die Anzahl der Knoten in beiden Bäumen ist gleich, ungerade und liegt im Bereich [1, 4999].
Node.val ist „+” oder ein englischer Kleinbuchstabe.
Es ist garantiert, dass der angegebene Baum ein gültiger binärer Ausdrucksbaum ist.

Hinweise:
Zählen Sie für jede Variable, wie oft sie im ersten Baum vorkam.
Machen Sie dasselbe für den zweiten Baum und prüfen Sie, ob die Anzahl für beide Bäume gleich ist.

Tiefensuchalgorithmus mit Hash-Tabelle

Da der Ausdrucksbaum binär ist und nur ein Pluszeichen enthalten kann. Daher können wir den Tiefensuchalgorithmus (DFS) auf beiden binären Ausdrucksbäumen ausführen und jede Variable zählen. Die beiden Ausdrucksbäume sind gleich, wenn beide Bäume die gleiche Anzahl von Variablen enthalten.

Das DFS läuft in O(N)-Zeit, wobei N die Anzahl der Knoten in beiden binären Ausdrucksbäumen ist. Die Raumkomplexität ist O (N), da wir Stack über Rekursion verwenden und auch die Zähler für jede Variable aufzeichnen müssen.

Um zu vergleichen, ob zwei Hash-Maps gleich sind (unordered_map ), können wir sie einfach in C++ mit dem doppelten Gleichheitszeichen vergleichen.