Alles klar, Leute, mir wurde diese Frage heute in einem Interview gestellt und es geht so:
"Sagen Sie, ob ein Binärbaum in einem anderen Binärbaum enthalten ist oder nicht (enthält enthält sowohl die Struktur als auch den Wert der Knoten)"
Ich dachte an den folgenden Ansatz:
Reduziere den größeren Baum wie folgt:
%Vor% (Ich habe tatsächlich Code dafür geschrieben, {-} impliziert einen leeren linken oder rechten Teilbaum, jeder Teilbaum ist in {} paranthesis eingeschlossen)
Jetzt für kleinere Unterbaum müssen wir dieses Muster anpassen:
%Vor% Dabei steht {.*} für einen leeren oder nicht leeren Unterbaum.
Zu der Zeit, als ich dachte, wird dies ein triviales Regex-Pattern-Matching-Problem in Java sein, aber ich bin verblüfft. Jetzt habe ich das Gefühl, ich habe das Problem einfach umgestaltet (ein Monster aus einem anderen erschaffen).
Gibt es einen einfachen Regex-Liner, der zu diesen Mustern passt? Ich verstehe, dass es andere Ansätze geben könnte, um dieses Problem zu lösen, und das ist vielleicht nicht das Beste. Ich frage mich nur, ob das lösbar ist.
Ich bin mir nicht sicher, was der Interviewer genau meinte, "in einem anderen binären Baum enthalten". Wenn der Interviewer nach einer Methode fragt, um zu überprüfen, ob A ein Teilbaum von B ist, ist hier eine Methode, die überhaupt keine Regex benötigt:
Der Grund, warum Sie die Nullblätter einschließen möchten, ist, dass, wenn mehrere Knoten den gleichen Wert haben, die Vorbestellung und die Inorder möglicherweise nicht ausreichen. Hier ist ein Beispiel:
%Vor%Sie können dies auch überprüfen:
Prüft Unterstrukturen mit Preorder- und Inorder-Strings
Lesen Sie dies auch für weitere Informationen zu Vororder- und Inorder-Traversalen von Binärbäumen:
Wenn er jetzt NICHT nur Unterbäume meinte, könnte das Problem komplizierter werden, je nachdem, was der Interviewer mit einem "Teil" meinte. Sie könnten die Frage als Teilgraphen-Isomorphie-Problem betrachten (Bäume sind nur eine Teilmenge von Graphen) und dies ist NP-vollständig.
Es gibt möglicherweise bessere Ansätze, da Bäume viel eingeschränkter und einfacher sind als Diagramme.
Sie können dies tun, indem Sie wie in den anderen Antworten beschrieben eine Teilzeichenkette verwenden und nur eine Traversierung (Vorbestellung, Reihenfolge oder Nachbestellung) verwenden, solange Sie es sind Drucken der -Entity jedes Knotens in der Struktur, nicht nur ihrer Werte. Zum Beispiel ist ein Binärbaum entweder
null oder (value left-tree right-tree) drucken, wobei left-tree und right-tree durch die Darstellung der linken und rechten Teilbäume ersetzt werden. Jeder Baum hat jetzt eine eindeutige gedruckte Darstellung, und so ist ein Baum T ein Unterbaum eines Baums S wenn und nur wenn Die Zeichenfolgendarstellung von T ist eine Teilzeichenfolge der Zeichenfolgendarstellung von S .
Zum Beispiel der Baum
%Vor%wird als
dargestellt %Vor%und Sie können überprüfen, dass die Teilbäume dieses Baums Zeichenfolgen
haben %Vor%, von denen jede eine Teilzeichenfolge der Zeichenfolge für den gesamten Baum ist.
Die einzigen Vorbehalte sind natürlich Fälle, in denen die String-Repräsentationen der Werte die Serialisierung der Bäume stören (zB enthalten die Wert-Strings Leerzeichen oder Klammern, & amp; c.), um das robust zu machen, Ich möchte geeignete Maßnahmen mit Begrenzern oder Fluchten treffen.
Beachten Sie auch, dass nicht jeder String, der ein Teilstring eines Baumes ist, einem Teilstring eines Baumes entspricht. Zum Beispiel ist der String null) (E ein Teilstring des Baumes, entspricht jedoch keinem Teilbaum des Baumes; Nur wenn eine Zeichenkette s die Repräsentation einer Struktur t ist, bedeutet das, dass wenn s eine Zeichenkette der Zeichenkette s 'ist eines Baums t t ist ein Unterbaum von t .
Streng genommen ist Regex nicht für verschachtelte Klammern geeignet. Die Verschachtelung kann mithilfe von rekursiven regulären Ausdrücken angepasst werden, aber die Regex-Engine von Java unterstützt keine rekursiven Ausdrücke. In PERL oder PHP könnten Sie ein Muster wie
verwenden %Vor%entspricht einer bestimmten Baumstruktur, aber Sie können die Werte der untergeordneten Knoten nicht auf bestimmten Ebenen angeben.
Es gibt also leider keine einfache Zeile Regex, die dieses Problem lösen wird. Regex ist nicht das Werkzeug, das Sie für diesen Job benötigen.
Um diese Frage zu beantworten, würde ich empfehlen, Ihren großen Baum und kleinen Baum zu konstruieren und dann largeTree.contains(smallTree) mit der folgenden Klasse aufzurufen:
Im schlimmsten Fall wird eine Traversierung des kleinen Baums für jeden Knoten des großen Baums durchgeführt, wobei O(m * log n) ist, wobei m die Größe des großen Baums und n die Größe des kleinen Baums ist. Der schlimmste Fall kann erreicht werden, wenn jedes Element des großen und des kleinen Baums gleich ist und der kleine Baum tatsächlich einen Knoten größer ist als der große Baum.
Tags und Links java regex puzzle binary-tree