Path Sum

+10

On te donne un arbre binaire stocké dans le tableau tree en ordre par niveaux, ainsi qu’un nombre targetSum. La racine se trouve à l’index 0, les enfants du nœud à l’index i se trouvent aux index 2*i+1 (à gauche) et 2*i+2 (à droite), -1 indique une position vide, et le tableau peut se terminer par des entrées -1 supplémentaires. Renvoie true si un chemin de la racine à une feuille contient des valeurs dont la somme est égale à targetSum, et false sinon. Une feuille est un nœud sans enfants : les deux positions de ses enfants sont vides.

Fonction

hasPathSum(tree: integer-array, targetSum: integer) → boolean

treeinteger-array: l’arbre binaire dans l’ordre par niveaux, avec -1 pour une position vide
targetSuminteger: le total qu’un chemin de la racine à une feuille doit atteindre
Renvoieboolean: vrai si un chemin de la racine à une feuille a une somme égale à targetSum, faux sinon

Contraintes

1 ≤ tree.length ≤ 32767
Chaque tree[i] est égal à -1 ou à une valeur telle que 0 ≤ tree[i] ≤ 1000.
tree[0] n’est jamais -1, donc l’arbre comporte au moins un nœud.
L’array peut se terminer par des entrées -1 supplémentaires après le dernier nœud.
Les deux enfants d’un emplacement vide sont également vides, et la profondeur est au maximum de 14.
0 ≤ targetSum ≤ 15000

Exemples

Entrée: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 14
Sortie: true
Explication: Le chemin 3, 9, 2 (indices 0, 1, 4) totalise 14, et le 2 à l’index 4 est une feuille.

Entrée: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 12
Sortie: false
Explication: 3 + 9 = 12, mais le 9 a un enfant, donc aucun chemin ne s’y termine. Les trois chemins de la racine à une feuille donnent 14, 10 et 16, et aucun d’eux ne vaut 12.

Entrée: tree = [4, -1, -1]targetSum = 4
Sortie: true
Explication: Les deux emplacements enfants de la racine sont vides, donc la racine est une feuille à elle seule. Le chemin qui ne contient que 4 totalise 4.

+14 tests cachés à la soumission

Pour aller plus loin

Peux-tu compter les chemins dont la somme est égale à targetSum, sachant qu’un chemin peut commencer à n’importe quel nœud et se terminer à n’importe quel nœud situé en dessous, et pas seulement aller de la racine à une feuille ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La question porte sur les chemins complets, de la racine jusqu’à une feuille. Un total cumulé peut atteindre targetSum en cours de route, à un nœud qui a encore des enfants, et cela ne compte pas. Tu transmets donc la somme du chemin parcouru jusqu’ici à chaque nœud et tu la compares à la cible uniquement aux feuilles. La récursion transmet cette somme comme paramètre ; une pile la stocke à côté de chaque nœud.

Récursion sur la somme restante

Intuition

Tout d’abord, voyons comment se déplacer dans le tableau. Le nœud à l’index i a son enfant gauche à l’index 2*i+1 et son enfant droit à l’index 2*i+2. Un enfant est réel uniquement si son index se trouve dans le tableau et que la valeur à cet emplacement n’est pas -1. Dans [3, 9, 6, -1, 2, 1, 7], la racine 3 a des enfants aux index 1 et 2, et le 9 à l’index 1 a un emplacement gauche vide à l’index 3 et le 2 à l’index 4 à sa droite.

Passons maintenant à l’idée. Un chemin dont la somme vaut targetSum commence par la valeur de la racine. Le reste du chemin, qui commence par l’un des enfants de la racine, doit donc avoir pour somme targetSum moins cette valeur. C’est la même question sur un arbre plus petit. Soustrayez la valeur de chaque nœud au fur et à mesure de la descente. À une feuille, le chemin se termine : la réponse indique alors s’il ne reste rien.

Dans le premier exemple, la racine laisse 14 - 3 = 11, le 9 laisse 2, et la feuille 2 laisse 0 : true. Dans le deuxième exemple, le 9 laisse déjà 0, mais il a un enfant, donc la recherche continue, et sa feuille aboutit à -2. Chaque nœud est visité au plus une fois, soit un temps de O(n), et la pile d’appels contient un cadre par niveau, soit O(h), avec au plus 15 cadres ici (une profondeur de 14 compte les arêtes sous la racine).

Algorithme

Écris walk(i, remaining) et soustrais tree[i] de remaining.
Si les deux emplacements d’enfant de i sont vides (indice au-delà de la fin ou -1), renvoie si remaining vaut 0.
Sinon, renvoie true si l’appel à walk sur un enfant gauche réel ou sur un enfant droit réel renvoie true.
Renvoie walk(0, targetSum).

def hasPathSum(tree, targetSum):
    n = len(tree)

    def walk(i, remaining):
        # remaining is what the path still needs once it reaches node i.
        remaining -= tree[i]
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right:
            return remaining == 0  # a leaf: the path ends here
        return (has_left and walk(left, remaining)) or (has_right and walk(right, remaining))

    return walk(0, targetSum)

Recherche en profondeur avec une pile explicite

Intuition

La récursion conserve un nombre à chaque appel : la quantité cible qu’il reste à atteindre. Tu peux conserver toi-même un tel nombre sur une pile, à côté de chaque nœud, et supprimer les appels. Stocke la somme du chemin depuis la racine jusqu’au nœud, nœud inclus. Commence par (0, tree[0]), et attribue à chaque enfant la somme de son parent plus sa propre valeur.

Dépile une paire. Si le nœud est une feuille et que sa somme est égale à targetSum, tu as terminé. Sinon, empile ses vrais enfants. Dans le premier exemple, le côté droit sort de la pile en premier : les feuilles 7 et 1 portent les sommes 16 et 10. Puis (1, 12) pour le 9 est dépilé. Ce n’est pas une feuille, il empile donc (4, 14), une feuille dont la somme est la bonne.

Chaque nœud réel est empilé une fois, donc le temps d’exécution est O(n), et la recherche s’arrête à la première feuille qui correspond. La pile contient les frères et sœurs en attente le long du chemin actuel, environ un par niveau, soit un espace de O(h). La même boucle fonctionne sur un arbre profond basé sur des pointeurs, pour lequel la récursion pourrait manquer de place dans la pile.

Algorithme

Empilez (0, tree[0]).
Dépilez une paire (i, total) et examinez les positions des enfants 2*i+1 et 2*i+2.
Si aucun des deux enfants n’existe et que total est égal à targetSum, renvoyez true.
Empilez chaque enfant existant c sous la forme (c, total + tree[c]).
Lorsque la pile est vide, renvoyez false.

def hasPathSum(tree, targetSum):
    n = len(tree)
    stack = [(0, tree[0])]  # (node index, sum of the path from the root to it)
    while stack:
        i, total = stack.pop()
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right and total == targetSum:
            return True  # a leaf whose path adds up
        if has_left:
            stack.append((left, total + tree[left]))
        if has_right:
            stack.append((right, total + tree[right]))
    return False

Pièges et cas limites

Presque tous les bogues de ce problème concernent l’endroit où un chemin se termine.

Comparer la somme à chaque nœud. Dans le deuxième exemple, 3 + 9 = 12 correspond à la somme au nœud 9, qui a un enfant : la réponse est donc false. Compare uniquement aux feuilles.
Considérer un emplacement d’enfant vide comme la fin d’un chemin. Si walk sur un emplacement vide renvoie remaining == 0, le 9 du deuxième exemple est considéré comme une feuille via son emplacement d’enfant gauche vide. Un nœud est une feuille uniquement lorsque ses deux emplacements sont vides.
Oublier la racine seule. Un nœud unique est une feuille : [4] avec targetSum = 4 renvoie donc true, tout comme [0] avec targetSum = 0.
Arrêter la recherche dès que le total dépasse la cible. Les valeurs ne sont jamais négatives ici, donc cette méthode est sûre pour ce problème, mais le même code donne de mauvaises réponses dès qu’un arbre peut contenir des valeurs négatives.
Lire au-delà de la fin. Une feuille située près de la fin du tableau peut avoir des indices d’enfant qui dépassent sa dernière entrée, car le tableau peut s’arrêter juste après le dernier nœud. Vérifie l’indice avant de lire tree[c].
Confondre le décalage en Lua et en R, où les tableaux commencent à 1. Garde les indices des nœuds à base 0 pour le calcul 2*i+1 et lis tree[i + 1].

Questions fréquentes4

Quelle est la complexité temporelle de Path Sum ?

Chaque nœud est visité au plus une fois, donc la complexité temporelle est O(n), et la recherche peut s’arrêter à la première feuille qui correspond. L’espace supplémentaire est de O(h) pour le chemin exploré, que ce soit sous forme de cadres d’appel ou d’entrées dans votre propre pile.

Pourquoi Path Sum vérifie-t-il la somme uniquement aux nœuds feuilles ?

Le problème demande un chemin de la racine à une feuille, et un chemin qui s’arrête à un nœud ayant des enfants n’en est pas un. Vérifier à chaque nœud renvoie true trop souvent, par exemple lorsque la valeur de la racine seule est égale à la cible, mais que la racine a un enfant. Un nœud termine un chemin uniquement lorsque ses deux emplacements d’enfant sont vides.

Peut-on résoudre Path Sum avec un parcours en largeur (BFS) ?

Oui. Placez les paires composées d’un nœud et de la somme du chemin correspondant dans une file plutôt que dans une pile, puis vérifiez chaque feuille à mesure qu’elle en sort. Le temps reste O(n), mais la file peut contenir un niveau entier, soit environ la moitié des nœuds d’un arbre complet, tandis qu’une pile contient environ un nœud par niveau.

Comment trouver tous les chemins dont la somme est égale à la cible ?

Conservez la liste des nœuds du chemin actuel à mesure que vous descendez, copiez-la dans la réponse à chaque feuille dont la somme correspond, puis retirez le dernier nœud lorsque vous remontez. Le parcours reste le même ; seule la gestion des données supplémentaires s’alourdit. La copie des chemins peut coûter plus cher que le parcours lui-même lorsque de nombreuses feuilles correspondent.

Python

def hasPathSum(tree, targetSum):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

tree = [3, 9, 6, -1, 2, 1, 7]
targetSum = 14

Attendu

true