99. Recover Binary Search Tree
ou comment démêler un sac de nœuds 🧶
Hi 👋
Cette semaine on se retrouvait pour un problème sur les arbres binaires: le 99. Recover Binary Search Tree 🔗; un problème de difficulté medium.
Voyons de quoi il en retourne:
L’énoncé ✍️
Étant donné le nœud racine (root) d’un arbre de recherche binaire (BST) où exactement deux nœuds on été échangés par erreur; Reformez l’arbre sans en changer sa structure.
Follow up: Pouvez-vous trouver une solution en O(1) espace mémoire?
L’intuition
Cet énoncé invite à reconsidérer la définition d’un arbre de recherche binaire, ou binary search tree (BST).
Dans un BST:
L’enfant gauche est plus petit que son parent.
L’enfant droit est plus grand que son parent.
En parcourant un BST inorder, c’est à dire, en commençant par traiter l’enfant gauche, puis le nœud parent et enfin l’enfant droit, on obtient une liste triée d’entiers croissants.
| def inorder(n: 'TreeNode') -> None: | |
| if n == None: | |
| return | |
| inorder(n.left) | |
| # Node processing: here simple print | |
| print(n.val) | |
| inorder(n.right) |
Un exemple:
On adapte cette fonction de parcours d’arbre inorder en ajoutant deux variables pour traquer les nœuds ne vérifiant pas les propriétés d’un BST. Appelons les deux nœuds pour lesquels nous devons échanger les valeurs swap_a et swap_b.
On a également besoin de suivre le nœud parent lors de notre parcours d’arbre pour vérifier si les enfants vérifient ou non les propriétés d’un BST. Appelons cette variable parent.
Une fois trouvé les deux nœuds non conformes, on échange leur valeur pour rétablir un BST valide.
| class Solution: | |
| def __init__(self): | |
| self.swap_a = None | |
| self.swap_b = None | |
| self.parent = TreeNode(float('-inf')) | |
| def inorder(self, n: TreeNode) -> None: | |
| if n == None: | |
| return | |
| self.inorder(n.left) | |
| if self.swap_a == None and self.parent.val >= n.val: | |
| self.swap_a = self.parent | |
| if self.swap_a != None and self.parent.val >= n.val: | |
| self.swap_b = n | |
| self.parent = n | |
| self.inorder(n.right) | |
| def recoverTree(self, root: TreeNode) -> None: | |
| """ | |
| Do not return anything, modify root in-place instead. | |
| """ | |
| self.inorder(root) | |
| self.swap_a.val, self.swap_b.val = self.swap_b.val, self.swap_a.val | |
Analyse de la complexité
Espace mémoire: On utilise une récursion, on maitient donc une call stack de façon implicite dans ce programme. La taille de cette call stack est de
O(log(n))en moyenne dans le cas d’un arbre équilibré et deO(n)dans le cas d’un arbre binaire totalement déséquilibré.
O(log(n) et un arbre totalement déséquilibré O(n), n étant le nombre de noeuds. Création de l’auteur.Temps d’exécution: le parcours en profondeur d’un arbre (DFS) inorder prend
O(V + E), avecVle nombre de neouds (vertex) etEle nombre d’arc (edge).
Walkthrough vidéo
As usual, le condensé de la séance avec le walkthrough de la résolution est disponible sur notre chaîne 📺
Wrap up
Un bon exercise de parcours d’abre où le challenge était sur la façon de suivre et de mettre à jour les noeuds ne vérifiant pas les conditions d’un BST. Ici, nos trois variables swap_a, swap_b et parent nous ont permis, combinées à une DFS inorder, de rétablir un arbre binaire de recherche.
Samedi prochain: on continue sur les arbres avec le problème 968. Binary Tree Cameras. RDV 09h30 sur notre twitch 😉
Stay safe & see you next week,
Your friends at leetgrind
Note: Pour le follow-up en O(1) space, ce discuss propose une bonne piste de résolution en utilisant une traversée via la méthode de Morris.
Photo de thumbnail par Flickr de Pexels
Thanks to qwl5004 for the layout of the solution!