Kotlin Binary Tree Preorder Traversal (une solution récursive et sans utiliser la récursivité)

Cet article concerne la traversée pré-ordonnée d'un arbre binaire, une méthode de traversée de l'arbre dans laquelle le nœud actuel est visité avant ses enfants. L'algorithme de parcours de préordre visite d'abord le nœud racine, puis visite récursivement le sous-arbre gauche, suivi du sous-arbre droit. Le résultat d'un parcours de préordre est une liste des valeurs des nœuds dans l'ordre dans lequel ils sont visités. Cet article vous aidera à comprendre comment parcourir un arbre binaire et également comment l'implémenter de différentes manières.

La traversée de préordre est une méthode de traversée d'un arbre binaire où le nœud actuel est visité avant ses enfants. L'algorithme visite d'abord le nœud racine, puis visite récursivement le sous-arbre gauche, suivi du sous-arbre droit. Le résultat d'un parcours de préordre est une liste des valeurs des nœuds dans l'ordre dans lequel ils sont visités.

Dans ce problème, on vous donne la racine d'un arbre binaire représenté par la classe TreeNode dans Kotlin, qui a une propriété val pour la valeur du nœud et des propriétés left et right pour ses enfants gauche et droit, respectivement. Votre tâche consiste à écrire deux implémentations d'une fonction qui effectue un parcours de préordre de l'arbre binaire et renvoie une liste des valeurs des nœuds. L'un doit être une solution récursive et l'autre ne doit pas utiliser la récursivité.

Voici la signature de classe de la fonction :

 fun preorderTraversal(root: TreeNode?): List<Int>

L'entrée de la fonction est le nœud racine de l'arbre binaire et la sortie est une liste d'entiers représentant les valeurs des nœuds dans l'ordre dans lequel ils sont visités lors du parcours de préordre.

Descriptifs :

Étant donné la racine d'un arbre binaire, renvoie le parcours de préordre des valeurs de ses nœuds. Faites cela à la fois avec une solution récursive et sans utiliser la récursivité.

 class TreeNode(var `val`: Int) { var left: TreeNode? = null var right: TreeNode? = null }

Voici une solution récursive au problème :

 fun preorderTraversal(root: TreeNode?): List<Int> { val result = mutableListOf<Int>() if (root == null) return result result.add(root.val) result.addAll(preorderTraversal(root.left)) result.addAll(preorderTraversal(root.right)) return result }

Cette fonction effectue un parcours pré-ordonné de l'arbre binaire et renvoie une liste des valeurs des nœuds dans l'ordre dans lequel ils sont visités.

L'algorithme fonctionne comme suit:

1. Si le nœud racine est nul, renvoie une liste vide.
2. Ajoutez la valeur du nœud racine à la liste des résultats.
3. Parcourez récursivement le sous-arbre gauche en appelant la fonction sur l'enfant gauche de la racine et ajoutez la liste renvoyée à la liste de résultats.
4. Parcourez récursivement le sous-arbre droit en appelant la fonction sur l'enfant droit de la racine et ajoutez la liste renvoyée à la liste de résultats.
5. Renvoie la liste des résultats.

Cet algorithme a une complexité temporelle de O(n), où n est le nombre de nœuds dans l'arbre, et une complexité spatiale de O(h), où h est la hauteur de l'arbre (due à la pile d'appels).

Voici une solution utilisant une approche itérative (c'est-à-dire sans utiliser la récursivité):

 fun preorderTraversal(root: TreeNode?): List<Int> { val result = mutableListOf<Int>() val stack = Stack<TreeNode>() var current = root while (current != null || stack.isNotEmpty()) { while (current != null) { result.add(current.val) stack.push(current) current = current.left } current = stack.pop() current = current.right } return result }

Cette fonction effectue un parcours pré-ordonné de l'arbre binaire et renvoie une liste des valeurs des nœuds dans l'ordre dans lequel ils sont visités. Il utilise une pile pour garder une trace des nœuds qui doivent encore être visités.

L'algorithme fonctionne comme suit:

1. Initialisez une pile vide et définissez le nœud actuel sur la racine de l'arborescence.

2. Tant que le nœud actuel n'est pas nul ou que la pile n'est pas vide :

   1. Tant que le nœud actuel n'est pas nul :

      1. Ajoutez la valeur du nœud actuel à la liste des résultats.
      2. Poussez le nœud actuel sur la pile.
      3. Définit le nœud actuel sur son enfant gauche.

   2. Détachez le nœud supérieur de la pile et définissez le nœud actuel sur son enfant droit.

3. Renvoie la liste des résultats.

Cet algorithme a une complexité temporelle de O(n), où n est le nombre de nœuds dans l'arbre, et une complexité spatiale de O(h), où h est la hauteur de l'arbre.

J'espère que ça aide! Faites-moi savoir si vous avez d'autres questions.