. Traversée post-commande de l'arbre binaire

145. Traversée post-commande de l'arbre binaire

Difficulté :Facile

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

Étant donné la racine d'un arbre binaire, renvoie le parcours post-ordre des valeurs de ses nœuds.

Exemple 1 :

• Entrée : root = [1,null,2,3]
• Sortie : [3,2,1]

Exemple 2 :

• Entrée : root = []
• Sortie : []

Exemple 3 :

• Entrée : racine = [1]
• Sortie : [1]

Contraintes :

• Le nombre de nœuds dans l'arborescence est compris entre [0, 100].
• -100 <= Node.val <= 100

Solution :

On peut utiliser une approche itérative avec une stack. Le parcours post-ordre suit l'ordre : Gauche, Droite, Racine.

Implémentons cette solution en PHP : 145. Traversée post-ordre d'arbre binaire

val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}
/**
* @param TreeNode $root
* @return Integer[]
*/
function postorderTraversal($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:

// Example 1
$root1 = new TreeNode(1);
$root1->right = new TreeNode(2);
$root1->right->left = new TreeNode(3);
print_r(postorderTraversal($root1)); // Output: [3, 2, 1]

// Example 2
$root2 = null;
print_r(postorderTraversal($root2)); // Output: []

// Example 3
$root3 = new TreeNode(1);
print_r(postorderTraversal($root3)); // Output: [1]
?>





  
  
  Explication:



Classe TreeNode : La classe TreeNode définit un nœud dans l'arborescence binaire, y compris sa valeur, son enfant gauche et son enfant droit.

Fonction postorderTraversal :


On initialise un tableau de résultats vide et une pile.
Nous utilisons une boucle while qui continue tant que la pile n'est pas vide ou que le nœud actuel n'est pas nul.
Si le nœud actuel n'est pas nul, nous le plaçons sur la pile et nous nous déplaçons vers son enfant de gauche.
Si le nœud actuel est nul, nous vérifions le nœud supérieur de la pile. S'il a un bon enfant que nous n'avons pas encore visité, nous passons au bon enfant. Sinon, nous ajoutons la valeur du nœud au tableau de résultats et la retirons de la pile.







Cette approche itérative simule le parcours post-ordre récursif sans utiliser la récursion du système, ce qui la rend plus efficace en termes de mémoire.

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!