Algorithmes et Structures de Données

Trouver la hauteur de l’arbre binaire

Étant donné un arbre binaire, vous devez en déterminer la hauteur. La hauteur d’un arbre binaire correspond à la hauteur de sa racine, c’est-à-dire le nombre maximal de niveaux de nœuds sous la racine.
Dans l’exemple à droite :
  • Les nœuds ayant pour valeurs 4, 6, 7 et 8 ont une hauteur de 1
  • Les nœuds ayant pour valeurs 3 et 5 ont une hauteur de 2
  • Le nœud ayant pour valeur 2 a une hauteur de 3
  • Le nœud racine ayant pour valeur 1 a une hauteur de 4.
notion image

Entrée

Les données d’entrée sont des entiers séparés par des espaces, qui représentent les valeurs des nœuds de l’arbre binaire. L’ordre de ces valeurs est déterminé en parcourant le sous-arbre de gauche à chaque fois avant de passer à celui de droite. Une valeur de 0 indique 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 la hauteur de l’arbre binaire.

Exemples

Entrée
Sortie
1 2 3 8 5 0 0 0 0 5 8 0 0 0 0
3
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0
4

Explications

Exemple 1 :
notion image
Exemple 2 :
notion image
 
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue