Spiegelbild eines n-ären Baumes? Kann mir jemand erklären?

Question

Diese Problemfrage bei Amazon Interview gestellt. Ich habe versucht, eine Lösung zu finden, aber ich habe keine Lösung gefunden. Jeder kann das Problem mit den Details lösen.

Answer 1

Dies ist eine ziemlich standardmäßige Interviewfrage.

Denken Sie über die Frage auf diese Weise nach, wenn Sie vor einem Spiegel mit Ihrem Baum standen, wie würde es aussehen. Ich würde Sie ermutigen, tatsächlich einen einfachen Baum zu zeichnen und vor dem Spiegel zu stehen und zu zeichnen, wie er aussieht.

Nachdem Sie dies getan haben, haben Sie vielleicht festgestellt, dass diese Frage fast identisch mit der Invertierung eines Baumes ist. Der Prozess der Inversion ist, auf jeder Ebene, den linken und den rechten Knoten zu vertauschen und weiter zu gehen, wenn und nur wenn der Kindknoten existiert.

Hier einige Pseudo-Code Ihnen den Einstieg:

invert_bst(bst): 
    bst's left node = bst's right node 
    if bst's left child is not null: 
     invert_bst(bst left child) 
    if bst's right child is not null: 
     invert_bst(bst right child) 

ich dringend, diese Lösung zu implementieren versuchen würde fördern.

Viel Glück bei Ihren zukünftigen Interviews!

Answer 2

Es ist ziemlich einfach, Spiegelbild bedeutet, dass der linke Knoten des ursprünglichen Knotens zum rechten Knoten für den Spiegelbildbaum wird. Sie können die Vorbestellung verwenden und den Knoten als links für das Original rechts für den Spiegel und rechts für das Original links für den Spiegel hinzufügen.

public Node createTreeMirror(Node root) { 
    if (root == null) { 
     return null; 
    } 
    Node mirror = new Node(root.data); 
    mirror.right = createTreeMirror(root.left); 
    mirror.left = createTreeMirror(root.right); 
    return mirror; 
}