L’arbre binaire est-il complet ?
On vous demande de déterminer si l’arbre binaire donné est complet.
Un arbre binaire est dit complet si tous les niveaux de l’arbre sont entièrement remplis, à l’exception du dernier niveau, dont les nœuds doivent être placés le plus à gauche possible.
Les deux arbres présentés ci-dessous sont des arbres binaires complets.
Entrée
L’entrée contient des entiers séparés par des espaces, représentant les valeurs des nœuds de l’arbre binaire. L’ordre des valeurs est donné comme décrit dans l’énoncé précédent (en parcourant chaque fois le sous-arbre gauche puis le sous-arbre droit). Une valeur de 0 signifie que le nœud n’existe pas. Il est garanti que l’arbre binaire fourni est valide.
Sortie
Le programme doit afficher
Yes si l’arbre binaire est complet, et No sinon.Exemples
Entrée | Sortie |
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0 | Yes |
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0 | Yes |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | No |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | No |
Explications
- L’exemple 1 est un arbre binaire complet, car le dernier niveau est rempli à partir de la gauche.
- L’exemple 2 est un arbre binaire complet, car le dernier niveau est rempli à partir de la gauche.
- L’exemple 3 n’est pas un arbre binaire complet, car il n’est pas rempli depuis la toute première position à gauche.
.png?table=block&id=18a2c681-664d-8141-a67c-e6b56dc8cd0a&cache=v2)
- L’exemple 4 n’est pas un arbre binaire complet, car il n’est pas rempli depuis la toute première position à gauche.
.png?table=block&id=18a2c681-664d-81a6-b9f3-e8df9c091e07&cache=v2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB