Parcours en post-ordre (post-order traversal) d’un arbre binaire
Le parcours en post-ordre d’un arbre est une procédure récursive où l’on visite d’abord le sous-arbre gauche d’un nœud, puis son sous-arbre droit, et enfin le nœud lui-même :
- Visiter le sous-arbre gauche (
node.left)
- Visiter le sous-arbre droit (
node.right)
- Visiter le nœud courant
Étant donné un arbre binaire, il vous est demandé de réaliser un parcours en post-ordre sur celui-ci.
Entrée
L’entrée contient des entiers séparés par des espaces qui représentent les valeurs des nœuds de l’arbre binaire. L’ordre des valeurs est donné en parcourant le sous-arbre gauche puis le sous-arbre droit à chaque fois. Une valeur de 0 signifie que le nœud n’existe pas. Il est garanti que l’arbre binaire fourni en entrée est valide.
Sortie
Le programme doit afficher les valeurs des nœuds de l’arbre binaire telles qu’elles apparaissent lors d’un parcours en post-ordre. Toutes les valeurs doivent être séparées par un espace.
Exemples
Input | Entrée |
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0 | 8 9 4 5 2 6 7 3 1 |
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0 | 8 4 5 2 6 7 3 1 |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | 4 5 2 6 8 9 7 3 1 |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | 4 7 8 5 2 6 3 1 |
Explication
- Exemple 1:
.png?table=block&id=18a2c681-664d-8182-832f-c0505bcc9f6a&cache=v2)
- Exemple 2:
.png?table=block&id=18a2c681-664d-8160-b912-c5f131120312&cache=v2)
- Exemple 3:
.png?table=block&id=18a2c681-664d-8147-b51d-d63d23708ae1&cache=v2)
- Exemple 4:
.png?table=block&id=18a2c681-664d-81fb-b955-f65a7642de15&cache=v2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB