. Inverser les arbres binaires équivalents

951. Retourner les arbres binaires équivalents

Difficulté :Moyen

Sujets : Arbre, recherche en profondeur d'abord, arbre binaire

Pour un arbre binaire T, nous pouvons définir une opération de retournement comme suit : choisissez n'importe quel nœud et échangez les sous-arbres enfants gauche et droit.

Un arbre binaire X est équivalent flip à un arbre binaire Y si et seulement si on peut rendre X égal à Y après un certain nombre d'opérations de retournement.

Étant donné les racines de deux arbres binaires root1 et root2, renvoie true si les deux arbres sont équivalents ou faux sinon.

Exemple 1 :

• Entrée : root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5 , nul, nul, nul, nul, 8,7]
• Sortie : vrai
• Explication : Nous avons inversé les nœuds avec les valeurs 1, 3 et 5.

Exemple 2 :

• Entrée : root1 = [], root2 = []
• Sortie : vrai

Exemple 3 :

• Entrée : root1 = [], root2 = [1]
• Sortie : faux

Contraintes :

• Le nombre de nœuds dans chaque arbre est compris entre [0, 100].
• Chaque arbre aura des valeurs de nœuds uniques comprises dans la plage [0, 99].

Solution :

Nous pouvons utiliser une recherche récursive en profondeur d'abord (DFS). L'idée est que deux arbres sont équivalents si leurs valeurs de racine sont les mêmes, et que les sous-arbres sont soit les mêmes (sans aucun retournement), soit ils deviennent identiques après avoir retourné les enfants gauche et droit à certains nœuds.

Plan:

1. Cas de base :

   • Si root1 et root2 sont nuls, ils sont trivialement équivalents.
   • Si un seul d'entre eux est nul, ils ne peuvent pas être équivalents.
   • Si les valeurs racine de root1 et root2 sont différentes, elles ne peuvent pas être équivalentes.

2. Cas récursif :

   • Vérifiez récursivement deux possibilités :
     1. Le sous-arbre gauche de root1 est équivalent au sous-arbre gauche de root2, et le sous-arbre droit de root1 est équivalent au sous-arbre droit de root2 (c'est-à-dire pas de retournement).
     2. Le sous-arbre gauche de root1 est équivalent au sous-arbre droit de root2, et le sous-arbre droit de root1 est équivalent au sous-arbre gauche de root2 (c'est-à-dire, retournez les enfants).

Implémentons cette solution en PHP : 951. Retourner les arbres binaires équivalents

<?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)
?>

Explication:

1. Classe TreeNode : La classe TreeNode représente un nœud dans l'arborescence binaire, avec un constructeur pour initialiser la valeur du nœud, l'enfant gauche et l'enfant droit.

2. Fonction flipEquiv :

   • Les cas de base gèrent lorsque les deux nœuds sont nuls, lorsqu'un est nul ou lorsque les valeurs ne correspondent pas.
   • Le cas récursif vérifie les deux possibilités (pas de retournement ou retournement), garantissant que les sous-arbres sont équivalents dans les deux conditions.

Complexité temporelle :

• La fonction vérifie chaque nœud dans les deux arbres et chaque appel récursif traite deux sous-arbres. Par conséquent, la complexité temporelle est O(N), où N est le nombre de nœuds dans l'arbre.

Complexité spatiale :

• La complexité spatiale est O(H), où H est la hauteur de l'arbre, à cause de la pile récursive. Dans le pire des cas (pour un arbre asymétrique), cela pourrait être O(N).

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!