. Traversée de vente par correspondance de l'arbre N-aire

590. Postcommande de l'arbre N-aire Traversa

Difficulté :Facile

Sujets : Pile, arbre, recherche en profondeur

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

La sérialisation des entrées Nary-Tree est représentée dans leur parcours par ordre de niveau. Chaque groupe d'enfants est séparé par la valeur nulle (Voir exemples)

Exemple 1 :

• Entrée : racine = [1,null,3,2,4,null,5,6]
• Sortie : [5,6,3,2,4,1]

Exemple 2 :

• Entrée : racine = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12 , nul, 13, nul, nul, 14]
• Sortie : [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

Contraintes :

• Le nombre de nœuds dans l'arborescence est compris entre [0, 100⁴].
• -100 <= Node.val <= 100⁴
• La hauteur de l'arbre n-aire est inférieure ou égale à 1000.

Suivi : La solution récursive est triviale, pourriez-vous la faire de manière itérative ?

Solution :

Nous pouvons l'aborder à la fois de manière récursive et itérative. Puisque le suivi demande une solution itérative, nous nous concentrerons sur cela. Le parcours post-ordre signifie visiter d'abord les nœuds enfants, puis le nœud parent.

Implémentons cette solution en PHP : 590. Traversée de post-commande de l'arbre N-aire

val = $val;
    }
}

/**
 * @param Node $root
 * @return integer[]
 */
function postorder($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1:
$root1 = new Node(1);
$root1->children = [
    $node3 = new Node(3),
    new Node(2),
    new Node(4)
];
$node3->children = [
    new Node(5),
    new Node(6)
];

print_r(postorder($root1)); // Output: [5, 6, 3, 2, 4, 1]

// Example 2:
$root2 = new Node(1);
$root2->children = [
    new Node(2),
    $node3 = new Node(3),
    $node4 = new Node(4),
    $node5 = new Node(5)
];
$node3->children = [
    $node6 = new Node(6),
    $node7 = new Node(7)
];
$node4->children = [
    $node8 = new Node(8)
];
$node5->children = [
    $node9 = new Node(9),
    $node10 = new Node(10)
];
$node7->children = [
    new Node(11)
];
$node8->children = [
    new Node(12)
];
$node9->children = [
    new Node(13)
];
$node11 = $node7->children[0];
$node11->children = [
    new Node(14)
];

print_r(postorder($root2)); // Output: [2, 6, 14, 11, 7, 3, 12, 8, 4, 13, 9, 10, 5, 1]
?>





  
  
  Explication:




Initialisation :


Créez une pile et poussez le nœud racine dessus.
Créez un résultat de tableau vide pour stocker le parcours final de post-commande.



Traversée :


Supprimez le nœud de la pile, insérez sa valeur au début du tableau de résultats.
Poussez tous ses enfants sur la pile.
Continuez jusqu'à ce que la pile soit vide.



Résultat :


Le tableau de résultats contiendra les nœuds dans l'ordre postérieur une fois la boucle terminée.




Cette approche itérative simule efficacement le parcours post-ordre en utilisant une pile et en inversant le processus généralement effectué par récursion.

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!