Invertieren eines Binärbaums in Java

Vor kurzem habe ich begonnen, einige LeetCode-Übungen zu üben, um meine Algorithmen-/Datenstrukturfähigkeiten zu verbessern. Ich kann sagen, dass die Plattform eine gute Umgebung bietet, um mit anderen Entwicklern Lösungen in mehreren Programmiersprachen zu üben und zu lernen, zu diskutieren, Lösungen mit anderen zu teilen und Code-Herausforderungen zu üben, die von großen Unternehmen gefordert werden.

Was ist LeetCode?

LeetCode ist eine Website, die Kandidaten bei der Vorbereitung auf Coding-Interviews unterstützt. Benutzer können Herausforderungen üben, indem sie die Codierungs- und Algorithmusprobleme der Plattform sowie vordefinierte Tests für die Lösung des Kandidaten verwenden. LeetCode ist neben HackerRank zu einer beliebten Ressource für technische Interviews und Programmierwettbewerbe geworden.

Meine Routine, Probleme zu lösen

Ich habe mir zum Ziel gesetzt, mindestens 3 Herausforderungen pro Tag zu lösen, und meine Art, an eine Lösung zu denken, beinhaltet mein iPad, einen Stift für Bildschirme und die Freeform-App. Ich versuche, Lösungen zu zeichnen und darüber nachzudenken, und das hilft mir sehr bei meinen Code-Einreichungen. Viele Herausforderungen klingen auf den ersten Blick schwierig, aber mit ein paar Minuten Nachdenken und Entwerfen der Lösung (ich empfehle, Ihren Denkprozess aufzuschreiben). Wenn ich nicht innerhalb von 30 Minuten die richtige Lösung finde, schaue ich mir die Beiträge anderer Entwickler an, um herauszufinden, wo meine Fehler liegen (manchmal ein kleiner Schritt, den ich in meinem Code vergessen habe). Auch wenn Ihre Lösung gut genug ist, empfehle ich Ihnen dringend, sich die Beiträge anderer anzusehen, um über andere Wege zur Lösung dieses Problems nachzudenken (einige mehr oder weniger effizient).

Das Problem der Umkehrung des Binärbaums

Vor ein paar Tagen stand ich bei LeetCode vor dem Problem „Binärbaum umkehren“, eine bekannte Herausforderung, die in einigen Vorstellungsgesprächen gefordert wurde und ein Problem, das ich bei der Teilnahme an einem Kurs über Datenstrukturen/Algorithmen an der Universität gesehen habe. Obwohl ich mich dieser Herausforderung nie in einem Vorstellungsgespräch gestellt habe und in meiner Arbeit noch nie explizit einen Binärbaum umkehren musste, konnte ich durch das Wissen, wie man einen Binärbaum umkehrt, mehr Erfahrung mit DS, Bäumen und Algorithmendenken sammeln und einige Techniken wie Rekursion üben.
Ich empfehle Ihnen, zu versuchen, dieses Problem zu lösen, bevor Sie den Rest dieses Artikels lesen

Die Lösung

Das Problem „Binärbaum umkehren“ forderte mich auf: „Wenn die Wurzel eines Binärbaums gegeben ist, invertieren Sie den Baum und geben Sie seine Wurzel zurück.“ (Mit anderen Worten, wir sollten den Baum „spiegeln“). Ich habe die Programmiersprache Java verwendet, um eine Lösung einzureichen, aber die Schritte sind für andere Sprachen dieselben (mit kleinen Syntaxänderungen). Das Eingabebeispiel und die erwartete Ausgabe werden unten angezeigt:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Wir werden die Rekursionstechnik verwenden, um die invertTree()-Methode rekursiv aufzurufen und dabei eine Seite des Baums als Wurzel zu übergeben. Da es bei jeder Rekursion darum geht, müssen wir eine Stoppbedingung definieren, bei der der Rekursionsstapel beendet wird und das entsprechende Ergebnis des Rekursionsaufrufs zurückgibt. Danach kehren wir einfach die Seiten des Baums um und weisen root.left den von der Rekursion zurückgegebenen Wert zu, indem wir root.right als Parameter übergeben, und machen dasselbe mit root.right, indem wir den Wert des Rekursionsergebnisses von root.left zuweisen. Da wir den ursprünglichen Wert ändern, benötigen wir eine Hilfsvariable, um das ursprüngliche Ergebnis von root.left zu speichern (Sie haben wahrscheinlich einen solchen Code an der Universität implementiert und ihn swap()-Methode genannt.

Am Ende geben wir die Wurzel mit invertierten Knoten zurück. Sie können den Code unten überprüfen:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }

        TreeNode aux = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(aux);

        return root;
    }
}

Denken Sie daran, dass es viele verschiedene Lösungen für verschiedene Probleme geben kann, und das ist großartig. Jeder hat eine eigene Denk- und Programmierweise, einen Datenstrukturbereich usw. Sie müssen nicht genau diesem Code folgen, um dieses Problem zu lösen, aber Sie müssen auf die Komplexität des Algorithmus achten (Sie können 3 verschachtelte Formeln verwenden, um ein Problem zu lösen). , aber das ist weniger performativ als die Verwendung von 1 für).

Das obige ist der detaillierte Inhalt vonInvertieren eines Binärbaums in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!