0Pricing
Coding Interview Prep · Leçon

Classe TreeNode et parcours BFS par niveaux

Construisez des arbres binaires à partir de tableaux, implémentez BFS avec une deque pour afficher les niveaux successifs et calculez la profondeur maximale avec BFS.

Classe TreeNode et parcours BFS par niveaux est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.

Fondements de la classe TreeNode

Un arbre binaire est une structure de données hiérarchique dans laquelle chaque nœud possède au plus deux enfants, appelés gauche et droit. En Python, nous représentons un nœud à l’aide d’une classe simple : class TreeNode: def __init__(self, val=0, left=None, right=None). Tous les problèmes d’arbres posés en entretien commencent par cette définition ; vous la retrouverez dans le code de base de presque tous les problèmes d’arbres de LeetCode.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Build a small tree manually:
#       1
#      / \
#     2   3
#    / \
#   4   5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(root.val, root.left.val, root.right.val)

Construire des arbres à partir de tableaux

Les problèmes d’entretien fournissent souvent un arbre représenté par un tableau en parcours par niveaux, où None indique les nœuds absents. Pour un indice i, l’enfant gauche se trouve à l’indice 2i+1 et l’enfant droit à l’indice 2i+2. Écrire une fonction utilitaire pour désérialiser ce tableau en nœuds TreeNodes reliés est un outil précieux qui fait gagner du temps pendant les séances d’entraînement.

from collections import deque

def build_tree(arr):
    if not arr or arr[0] is None:
        return None
    root = TreeNode(arr[0])
    q = deque([root])
    i = 1
    while q and i < len(arr):
        node = q.popleft()
        if i < len(arr) and arr[i] is not None:
            node.left = TreeNode(arr[i])
            q.append(node.left)
        i += 1
        if i < len(arr) and arr[i] is not None:
            node.right = TreeNode(arr[i])
            q.append(node.right)
        i += 1
    return root

root = build_tree([1, 2, 3, 4, 5, None, 6])
print(root.val, root.left.val, root.right.val)

Qu’est-ce que BFS et pourquoi une file ?

Le parcours en largeur (BFS) visite tous les nœuds à la profondeur d avant de visiter le moindre nœud à la profondeur d+1. Ce parcours niveau par niveau correspond exactement à ce que fournit une file (FIFO) : nous enfilons la racine, puis traitons les nœuds un par un en enfilant leurs enfants au fur et à mesure. En Python, collections.deque fournit appendleft et popleft en O(1), ce qui en fait un meilleur choix qu’une simple liste.

from collections import deque

def bfs_print(root):
    if not root:
        return
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.val, end=' ')
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
bfs_print(root)  # 1 2 3 4

BFS par niveaux : regrouper les niveaux

La variante standard de BFS regroupe les nœuds par niveaux en enregistrant la taille de la file au début de chaque itération. Traitez exactement ce nombre de nœuds, recueillez leurs valeurs, puis passez au niveau suivant. Vous obtenez ainsi une liste de listes — un format de sortie très courant lors des entretiens pour des problèmes comme le parcours d’un arbre binaire par niveaux, le parcours en zigzag et la vue du côté droit.

from collections import deque

def level_order(root):
    if not root:
        return []
    result = []
    q = deque([root])
    while q:
        level_size = len(q)
        level = []
        for _ in range(level_size):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(level)
    return result

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(level_order(root))  # [[1], [2, 3], [4]]

Profondeur maximale avec BFS

La profondeur maximale d’un arbre binaire est égale au nombre de niveaux de son parcours BFS. Il suffit de compter le nombre de fois où vous terminez une boucle de niveau. Vous obtenez une solution en O(n) en temps et en O(w) en espace, où w est la largeur maximale de l’arbre. Pour un arbre équilibré, w est en O(n/2), la complexité spatiale dans le pire cas est donc O(n).

from collections import deque

def max_depth_bfs(root):
    if not root:
        return 0
    depth = 0
    q = deque([root])
    while q:
        depth += 1
        for _ in range(len(q)):
            node = q.popleft()
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
    return depth

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(max_depth_bfs(root))  # 3

Vue du côté droit d’un arbre binaire

La vue du côté droit renvoie le dernier nœud visible lorsque vous regardez l’arbre depuis la droite — c’est-à-dire le dernier élément de chaque niveau lors du parcours BFS. Il s’agit d’une application directe du BFS par niveaux : recueillez le dernier nœud de chaque boucle de niveau. La complexité temporelle est O(n) et l’espace utilisé est O(w) pour la file.

from collections import deque

def right_side_view(root):
    if not root:
        return []
    result = []
    q = deque([root])
    while q:
        level_size = len(q)
        for i in range(level_size):
            node = q.popleft()
            if i == level_size - 1:
                result.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
    return result

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
print(right_side_view(root))  # [1, 3, 5]

Parcours par niveaux en zigzag

Dans le parcours en zigzag, les niveaux impairs sont parcourus de gauche à droite et les niveaux pairs de droite à gauche. L’implémentation la plus claire conserve la file de BFS telle quelle et se contente d’inverser alternativement les listes de chaque niveau avant de les ajouter au résultat. Suivez la direction à l’aide d’un indicateur booléen qui s’inverse à chaque niveau. Cela évite la complexité d’une file à double extrémité dans la boucle interne.

from collections import deque

def zigzag_level_order(root):
    if not root:
        return []
    result = []
    q = deque([root])
    left_to_right = True
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(level if left_to_right else level[::-1])
        left_to_right = not left_to_right
    return result

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(zigzag_level_order(root))

Analyse de la complexité spatiale de BFS

BFS utilise un espace O(w), où w représente la largeur maximale de l’arbre. Pour un arbre binaire parfait comportant n nœuds, le dernier niveau contient (n+1)/2 nœuds ; BFS peut donc conserver simultanément jusqu’à n/2 nœuds dans la file. Ainsi, BFS utilise davantage d’espace que DFS (O(h)) pour les arbres équilibrés et larges, mais moins pour les arbres profonds et dégénérés, où la profondeur de la pile d’appels de DFS atteint n.

# Space comparison: BFS vs DFS on a complete binary tree
# n=15 nodes, height=4
# BFS max queue size = 8 (last level)
# DFS max call stack = 4 (height)

# For a skewed tree (like a linked list):
# n=1000 nodes
# BFS max queue size = 1 (always 1 node per level)
# DFS max call stack = 1000 (recursion depth -> stack overflow!)

from collections import deque

def skewed_tree(n):
    root = TreeNode(1)
    cur = root
    for i in range(2, n+1):
        cur.right = TreeNode(i)
        cur = cur.right
    return root

root = skewed_tree(10)
print('BFS on skewed tree is safe')

Moyenne des niveaux d’un arbre binaire

Calculer la valeur moyenne de chaque niveau est une autre application directe de BFS. Additionnez toutes les valeurs d’un niveau, divisez le résultat par le nombre de nœuds, puis ajoutez-le à la liste des résultats. Cet exercice vérifie que vous savez effectuer des calculs arithmétiques dans la boucle parcourant les niveaux. Utilisez toujours une division en virgule flottante en Python 3 (l’opérateur /) et traitez le cas particulier de l’arbre vide dès le début.

from collections import deque

def average_of_levels(root):
    if not root:
        return []
    result = []
    q = deque([root])
    while q:
        size = len(q)
        total = 0
        for _ in range(size):
            node = q.popleft()
            total += node.val
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(total / size)
    return result

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(average_of_levels(root))  # [3.0, 14.5, 11.0]

Profondeur minimale avec BFS

La profondeur minimale est la distance entre la racine et la feuille la plus proche (un nœud sans enfant). BFS la trouve de manière optimale : le premier nœud feuille rencontré lors du parcours par niveaux se trouve nécessairement à la profondeur minimale. Retournez la profondeur courante dès que vous atteignez une feuille. La complexité est O(n) dans le pire des cas, mais le parcours se termine souvent bien plus tôt pour les arbres équilibrés.

from collections import deque

def min_depth(root):
    if not root:
        return 0
    q = deque([(root, 1)])
    while q:
        node, depth = q.popleft()
        # A leaf has no children
        if not node.left and not node.right:
            return depth
        if node.left:
            q.append((node.left, depth + 1))
        if node.right:
            q.append((node.right, depth + 1))
    return 0

root = TreeNode(2)
root.left = TreeNode(3)
root.left.left = TreeNode(4)
root.right = TreeNode(5)  # leaf at depth 2
print(min_depth(root))  # 2

Relier les nœuds voisins d’un même niveau

Le problème des pointeurs vers le voisin de droite vous demande de relier chaque nœud à son voisin de droite au même niveau. Avec BFS, c’est simple : dans la boucle consacrée à chaque niveau, définissez node.next = q[0] pour tous les nœuds sauf le dernier. C’est un exemple classique où BFS rend la solution évidente, tandis que DFS exige un suivi minutieux des pointeurs entre les sous-arbres.

from collections import deque

class Node:
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

def connect(root):
    if not root:
        return root
    q = deque([root])
    while q:
        size = len(q)
        for i in range(size):
            node = q.popleft()
            if i < size - 1:
                node.next = q[0]
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
    return root

print('BFS connect: O(n) time, O(w) space')

Vérification rapide

Testez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris la définition de la classe TreeNode et la construction d’arbres à partir de tableaux, le parcours BFS par niveaux à l’aide d’une file à double extrémité, avec l’astuce de la taille du niveau pour regrouper les nœuds, ainsi que des applications telles que la profondeur maximale, la profondeur minimale, la vue du côté droit, le parcours en zigzag et la moyenne des niveaux. Nous allons maintenant étudier les ordres de parcours récursifs de DFS.

Questions Fréquemment Posées

La leçon « Classe TreeNode et parcours BFS par niveaux » est-elle gratuite ?

Oui — le texte complet de « Classe TreeNode et parcours BFS par niveaux » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Classe TreeNode et parcours BFS par niveaux » ?

Construisez des arbres binaires à partir de tableaux, implémentez BFS avec une deque pour afficher les niveaux successifs et calculez la profondeur maximale avec BFS. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?

Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.

Combien de temps prend la leçon « Classe TreeNode et parcours BFS par niveaux » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?

Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Classe TreeNode et parcours BFS par niveaux
  2. DFS infixe, préfixe et postfixe
  3. Diamètre, hauteur et arbres équilibrés
  4. Somme des chemins et ancêtre commun le plus bas
← Retour à Coding Interview Prep