. Äquivalente Binärbäume umdrehen

951. Äquivalente Binärbäume umdrehen

Schwierigkeit:Mittel

Themen: Baum, Tiefensuche, Binärbaum

Für einen Binärbaum T können wir eine Flip-Operation wie folgt definieren: Wählen Sie einen beliebigen Knoten und tauschen Sie den linken und rechten untergeordneten Teilbaum aus.

Ein Binärbaum X ist Flip-Äquivalent zu einem Binärbaum Y genau dann, wenn wir X gleich Y nach einigen Flip-Operationen.

Angesichts der Wurzeln zweier Binärbäume root1 und root2 wird

true zurückgegeben, wenn die beiden Bäume äquivalent sind, andernfalls false.

Beispiel 1:

• Eingabe: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5 ,null,null,null,null,8,7]
• Ausgabe:wahr
• Erklärung:Wir haben bei Knoten mit den Werten 1, 3 und 5 umgedreht.

Beispiel 2:

• Eingabe: root1 = [], root2 = []
• Ausgabe:wahr

Beispiel 3:

• Eingabe: root1 = [], root2 = [1]
• Ausgabe:false

Einschränkungen:

Die Anzahl der Knoten in jedem Baum liegt im Bereich [0, 100].
Jeder Baum hat eindeutige Knotenwerte im Bereich [0, 99].

Lösung:

Wir können eine rekursive Tiefensuche (DFS) verwenden. Die Idee ist, dass zwei Bäume umkehräquivalent sind, wenn ihre Wurzelwerte gleich sind und die Teilbäume entweder gleich sind (ohne Umdrehungen) oder nach dem Umdrehen der linken und rechten Kinder an einigen Knoten gleich werden.

Planen:

1. Basisfälle:

   Wenn sowohl root1 als auch root2 null sind, sind sie trivialerweise Flip-Äquivalent.
   Wenn nur einer von ihnen null ist, können sie nicht gleichwertig sein.
   Wenn die Wurzelwerte von Wurzel1 und Wurzel2 unterschiedlich sind, können sie nicht gleichwertig sein.

2. Rekursiver Fall:

   Überprüfen Sie rekursiv zwei Möglichkeiten:
   • Der linke Teilbaum von Wurzel1 ist ein Spiegeläquivalent zum linken Teilbaum von Wurzel2, und der rechte Teilbaum von Wurzel1 ist ein Spiegeläquivalent zum rechten Teilbaum von Wurzel2 (d. h. kein Spiegeln).
     Der linke Teilbaum von Wurzel1 ist das Spiegeläquivalent zum rechten Teilbaum von Wurzel2, und der rechte Teilbaum von Wurzel1 ist das Spiegeläquivalent zum linken Teilbaum von Wurzel2 (d. h. die Kinder werden umgedreht).

Lassen Sie uns diese Lösung in PHP implementieren:

951. Äquivalente Binärbäume umdrehen

<?php
// Definition for a binary tree node.
class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

/**
 * @param TreeNode $root1
 * @param TreeNode $root2
 * @return Boolean
 */
function flipEquiv($root1, $root2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$root1 = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), new TreeNode(5, new TreeNode(7), new TreeNode(8))),
    new TreeNode(3, new TreeNode(6), null)
);

$root2 = new TreeNode(1,
    new TreeNode(3, null, new TreeNode(6)),
    new TreeNode(2, new TreeNode(4), new TreeNode(5, new TreeNode(8), new TreeNode(7)))
);

var_dump(flipEquiv($root1, $root2)); // Output: bool(true)
?>

Erläuterung:

1. TreeNode-Klasse: Die TreeNode-Klasse stellt einen Knoten im Binärbaum dar, mit einem Konstruktor zum Initialisieren des Knotenwerts, des linken und rechten Kindes.

2. flipEquiv-Funktion:

   • Die Basisfälle behandeln, wenn beide Knoten null sind, wenn einer null ist oder wenn die Werte nicht übereinstimmen.
   • Der rekursive Fall prüft beide Möglichkeiten (kein Flip vs. Flip) und stellt sicher, dass die Teilbäume unter beiden Bedingungen flipäquivalent sind.

Zeitkomplexität:

• Die Funktion prüft jeden Knoten in beiden Bäumen und jeder rekursive Aufruf verarbeitet zwei Teilbäume. Daher ist die Zeitkomplexität O(N), wobei N die Anzahl der Knoten im Baum ist.

Raumkomplexität:

• Aufgrund des rekursiven Stapels beträgt die Raumkomplexität O(H), wobei H die Höhe des Baums ist. Im schlimmsten Fall (für einen schiefen Baum) könnte dies O(N) sein.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt von. Äquivalente Binärbäume umdrehen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!