Hello les algoristes,
Aujourd’hui on se retrouvait pour un problème de notre arc “Arbre” pour le problème 297. Serialize and deserialize a Binary Tree 🔗, un problème classé difficile sur Leetcode qui va nous permettre de réviser les classiques 😉
Deux petites définitions avant de passer à la suite:
La serialization consiste à convertir une structure de données en un format qui peut être persisté sur le disque en une séquence de bits.
La deserialization correspond à l’étape inverse de la serialization, c’est-à-dire; lire une séquence de bits depuis le disque ou le réseau afin de reconstruire la structure de données initiale.
Ces précisions faites, nous pouvons attaquer le problème du jour!
L’énoncé
Ecrire un algorithme permettant de serializer et de deserializer un arbre binaire.
Assurez-vous que votre arbre soit sérializé sous forme de string et qu’il puisse être désérializé en un arbre identique à celui d’origine.
Pour ce faire, implémentez les méthodes
serialize
etdeserialize
de la classeCodec
.
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec: def serialize(self, root) -> str: """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ pass def deserialize(self, data: str) -> 'TreeNode': """Decodes your encoded data to „tree. :type data: str :rtype: TreeNode """ pass # Your Codec object will be instantiated and called as such: # ser = Codec() # deser = Codec() # ans = deser.deserialize(ser.serialize(root))
A vous de jouer … 😉
Résolution pas à pas
Un problème de serialization / deserialization nécessite de s’assurer que l’on perde aucune information sur la structure de données que l’on souhaite persister.
Ici, il s’agit d’un arbre binaire qui correspond à une collection de noeuds. Trois attributs caractérisent un noeud:
Sa valeur
val
Une référence vers son enfant gauche
left
Une référence vers son enfant droit
right
Serialization
La complexité réside dans la conservation de l’ordre des noeuds. Pour résoudre ce problème, on peut persister les noeuds d’un arbre niveau par niveau.
Concrètement, on persiste dans un string tous les noeuds de même profondeur avant de passer à l’étage suivant de l’arbre.
Cela se traduit dans l’implémentation par une double boucle while
:
Une première pour itérer sur l’intégralité de l’arbre via une BFS…
Une seconde boucle pour persister tous les noeuds d’un étage avant de passer au suivant.
def serialize(self, root) -> str: | |
queue, serialize = [root], "" | |
while queue: | |
next_level = [] | |
while queue: | |
node = queue.pop(0) | |
serialize += str(node.val) + "," if node else "null" + "," | |
if node: next_level.extend([node.left, node.right]) | |
queue = next_level if any(next_level) else [] | |
return serialize[:-1] |
Les snippets de code nous sont proposés par Vincent.
Deserialization
Pour reconstruire un arbre binaire à partir de la chaîne de caractères d’entrée, nous créons d’abord un TreeNode
pour chacun des entiers sérializés, voir la ligne 3.
Ensuite, le challenge est de reconstituer la filiation des différents noeuds.
def deserialize(self, data: str): | |
nodes = [TreeNode(int(s)) if s!= "null" else None for s in data.split(',')] | |
child = nodes[::-1] | |
root = child.pop() | |
for n in nodes: | |
if n and child: | |
n.left, n.right = child.pop(), child.pop() | |
return root |
Vincent nous propose une solution élégante dans laquelle on renverse la liste des noeuds dans child
afin de parcourir les nodes
et nous permettre d’accéder à ses enfants en poppant les éléments de child
. Brillant 😳
Le résume de la séance est disponible ici 👇
Des arbres et encore des arbres
La semaine prochaine, on continue sur notre arc “Arbre” avec le problème 124. Binary Tree Maximum Path Sum 🔗
As usual, rendez-vous 09:30am Paris time samedi prochain sur notre Twitch pour faire cet exercice ensemble 😎
A samedi prochain!
Your friends at LeetGrind,
Photo de thumbnail par Lerkrat Tangsri