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

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, renvoiele parcours post-ordre des valeurs de ses nœuds.

Exemple 1 :

. Binary Tree Postorder Traversal

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

Exemple 2 :

Entrée :racine = []
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 :

Nous pouvons 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-commande de l'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 :
          
           Nous initialisons 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 récursif de post-ordre sans utiliser la récursion du système, ce qui la rend plus efficace en mémoire.
Liens de contact
Si vous avez trouvé cette série utile, pensez à donner une étoile audépôtsur 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!