968. Binary Tree Cameras
Hello đ
Cette semaine, on continuait notre arc sur les arbres binaires avec le 968. Binary Tree Cameras đ; un problĂšme de difficultĂ© hard.
Voyons de quoi il en retourne:
LâĂ©noncĂ© âïž
Ătant donnĂ© le nĆud racine (root)
dâun arbre binaire T
. Nous installons des camĂ©ras de surveillance sur les nĆuds de T, oĂč chaque camĂ©ra peut surveiller le nĆud oĂč elle est installĂ©e, les 2 enfants immĂ©diats (left
& right
), et le nĆud parent.
Retournez le nombre minimum de camĂ©ras nĂ©cessaires pour surveiller tous les noeuds de lâarbre.
Lâintuition
Nous souhaitons installer un nombre minimum de camĂ©ras - cela revient Ă maximiser le nombre de nĆuds que chaque camĂ©ra peut surveiller. Et tous les nĆuds ne sont pas Ă©gaux pour cela:
Considérons une feuille (
leaf
) de T. Si on place une caméra surleaf
, nous ne pouvons surveiller que 2 nĆuds:leaf
, et son parent immĂ©diat.ConsidĂ©rons maintenant un nĆud parent dâune feuille (
leaf
). Si on place une camĂ©ra sur un tel nĆud, nous pouvons surveiller au maximum 3 noeuds:leaf
, ce nĆud, et son parent. Il est donc plus avantageux de placer une camĂ©ra sur ce nĆud au lieu deleaf
!
Nous privilĂ©gierions donc placer des camĂ©ras sur les nĆuds parents de nĆuds feuilles.
Et pour les autres nĆuds alors?
Pas Ă pas đŸ
Glad you asked!
Nous allons ainsi parcourir notre arbre T
de bas en haut - des leafs
jusquâĂ root
. On sait quâil est judicieux de commencer par placer des camĂ©ras sur les noeuds parents de leafs
: faire ainsi nous garantit un dĂ©part optimal pour lâalgorithme.
đĄ Si, Ă chaque Ă©tape, nous plaçons une camĂ©ra uniquement lorsque nĂ©cessaire - faisant ainsi un choix optimum local - , et nous avons commencĂ© de façon optimale, nous arriverons Ă la solution optimale: Ceci est le principe des âgreedy algorithmsâ.
đ Wiki:
âUn algorithme glouton (greedy algorithm en anglais, parfois appelĂ© aussi algorithme gourmand, ou goulu) est un algorithme qui suit le principe de faire, Ă©tape par Ă©tape, un choix optimum local, dans l'espoir d'obtenir un rĂ©sultat optimum global.â
En dĂ©tails đ
Nous allons implĂ©menter une version rĂ©cursive de la DFS, notre algorithme favori pour parcourir un arbre. Nous parcourons lâarbre jusquâĂ atteindre la premiĂšre leaf
(utilisant la call stack). Ă chaque fois que lâon dĂ©pile, on retourne une des 3 valeurs suivantes:
0: le nĆud que lâon quitte est une
leaf
, et ne comporte ainsi pas de camĂ©ras.1: ReprĂ©sente un un nĆud parent dâune feuille. On doit alors installer une camĂ©ra sur le nĆud actuel, pour surveiller les
leafs
en dessous.2: Le nĆud est dĂ©jĂ surveillĂ© par une autre camĂ©ra, pas besoin dâen installer une.
VoilĂ lâimplĂ©mentation:
class Solution: | |
def minCameraCover(self, root: TreeNode) -> int: | |
self.num_cameras = 0 | |
def dfs(root: TreeNode) -> int: | |
if not root: | |
# empty root, consider it monitored by a camera elsewhere | |
return 2 | |
left, right = dfs(root.left), dfs(root.right) # recurse down | |
if left == 0 or right == 0: | |
# this node is just above a leaf, | |
# so we install a camera on this node. | |
self.num_cameras += 1 | |
return 1 | |
elif left == 1 or right == 1: | |
# there's a camera below, which monitors this node | |
# so no need to install a camera here. | |
return 2 | |
else: | |
# any other case, | |
# treat it as a leaf node | |
return 0 | |
res = dfs(root) | |
if res == 0: | |
# root not covered, add 1 camera | |
self.num_cameras += 1 | |
return self.num_cameras |
Nâoublions pas de vĂ©rifier Ă la fin de la DFS que root
est bien surveillé par une caméra. Si non (la DFS retourne 0, considérant root
comme une leaf
), on ajoute alors une camera au compte total.
Voici une illustration de cet algorithme:
Et le walkthrough en vidĂ©o đ
Summer Break
La semaine prochaine sera le dernier épisode de la Saison 1 de LeetGrind, 14 épisodes au total! Nous allons réduire la voilure à un épisode toutes les 2 semaines jusque fin août et reviendrons frais en Septembre.
On revient aux bases pour ce dernier Ă©pisode la semaine prochaine: Dynamic Programming, avec le 740 Delete & Earn.
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,
Thumbnail photo de ATC Comm Photo