Überprüfen Sie, ob 2 Baumknoten (Vorfahr / Nachfahre) in O (1) mit der Vorverarbeitung verknüpft sind

Überprüfen Sie, ob zwei Baumknoten verwandt sind (d. H. Vorfahr-Nachfahre).

löse es in O (1) Zeit mit O (N) Raum (N = Anzahl der Knoten)Vorverarbeitung ist erlaubt

Das ist es. Ich gehe zu meiner Lösung (Ansatz) weiter unten. Bitte hören Sie auf, wenn Sie zuerst an sich selbst denken möchten.

Für eine Vorverarbeitung habe ich mich entschlossen, eine Vorbestellung zu machen (zuerst rekursiv durch die Wurzel gehen, dann Kinder) und jedem Knoten eine Bezeichnung zu geben.

Lassen Sie mich die Etiketten im Detail erklären. Jedes Etikett besteht aus durch Kommas getrennten natürlichen Zahlen wie "1,2,1,4,5" - die Länge dieser Sequenz entspricht(die Tiefe des Knotens + 1). Z.B. Die Bezeichnung der Wurzel ist "1", die Kinder der Wurzel haben Bezeichnungen "1,1", "1,2", "1,3" usw. Knoten der nächsten Ebene haben Bezeichnungen wie "1,1,1". , "1,1,2", ..., "1,2,1", "1,2,2", ...

Annehmen, dass "die Bestellnummer"eines Knotens ist die"1-basierter Index dieses Knotens"in der Kinderliste seiner Eltern.

Allgemeine Regel: Die Bezeichnung des Knotens besteht aus der übergeordneten Bezeichnung, gefolgt von Komma und "die Bestellnummer"des Knotens.

Um zu beantworten, ob zwei Knoten in O (1) verwandt sind (d. H. Vorfahr-Nachfahre), prüfe ich, ob die Bezeichnung von einem von ihnen "ein PräfixIch bin mir jedoch nicht sicher, ob solche Etiketten den Raum O (N) belegen.

Kritiker mit Korrekturen oder einem alternativen Ansatz werden erwartet.

Antworten auf die Frage(3)

Ihre Antwort auf die Frage