Path Sum

Q: Quelle est la complexité temporelle de Path Sum ?

O(n) : chaque nœud est visité au plus une fois, 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é, sous forme de cadres d’appel ou d’entrées dans votre propre pile.

FacileParcours d’arbre

+10

Tu reçois un arbre binaire stocké dans le tableau tree en parcours par niveaux, ainsi qu’un nombre targetSum. La racine se trouve à l’indice 0, les enfants du nœud à l’indice i se trouvent aux indices 2*i+1 (gauche) et 2*i+2 (droite), -1 indique un emplacement vide, et le tableau peut se terminer par des entrées -1 supplémentaires. Renvoie true s’il existe un chemin de la racine jusqu’à une feuille dont les valeurs totalisent targetSum, et false sinon. Une feuille est un nœud dont les deux emplacements d’enfant sont vides.

Fonction

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

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

Contraintes

1 ≤ tree.length ≤ 32767
Chaque tree[i] vaut -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.
Le tableau 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 plus 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’indice 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 se termine là. Les trois chemins de la racine à une feuille ont pour sommes 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 contient uniquement 4 totalise 4.

Pour aller plus loin

Peux-tu compter les chemins dont la somme est égale à targetSum si un chemin peut commencer à n’importe quel nœud et se terminer à n’importe quel nœud situé en dessous de celui-ci ?

Indices

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

0 sur 3 ouverts

Solution

Seuls les chemins complets comptent, de la racine jusqu’à une feuille. Un total cumulé peut atteindre targetSum à un nœud qui a encore des enfants, ce qui ne compte pas. Il faut donc transmettre la somme du chemin à chaque nœud, comme paramètre ou sur une pile, et la comparer à la cible uniquement aux feuilles.

Récursion sur la somme restante

Intuition

Un chemin dont la somme vaut targetSum commence par la valeur de la racine ; le reste, qui commence à l’un des enfants de la racine, doit donc avoir une somme égale à targetSum moins cette valeur. C’est la même question sur un arbre plus petit. Soustrais la valeur de chaque nœud en descendant ; à une feuille, le chemin se termine, donc la réponse est de savoir 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. Dans le deuxième, le 9 laisse déjà 0, mais il a un enfant, donc la recherche continue. Chaque nœud est visité une fois, en O(n) temps, et la pile d’appels contient une trame par niveau, au plus 15.

Algorithme

Écris walk(i, remaining) et soustrais tree[i] de remaining.
Si les deux emplacements des enfants de i sont vides (index au-delà de la fin ou -1), renvoie si remaining est égal à 0.
Sinon, renvoie true si walk appliqué à un véritable enfant gauche ou à un véritable enfant droit 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 par appel. Conserve-le plutôt toi-même, sur une pile à côté de chaque nœud : la somme du chemin de la racine jusqu’à ce nœud. Commence par (0, tree[0]) ; chaque enfant reçoit la somme de son parent plus sa propre valeur. Dépile une paire. Si le nœud est une feuille dont la somme est targetSum, tu as terminé ; sinon, empile ses enfants réels.

Chaque nœud réel est empilé une fois, en temps O(n), et la pile contient environ un frère en attente par niveau, soit O(h). La même boucle fonctionne sur un arbre profond basé sur des pointeurs, où la récursion pourrait épuiser la pile.

Algorithme

Empile (0, tree[0]).
Dépile une paire (i, total) et examine les positions des enfants 2*i+1 et 2*i+2.
Si aucun des deux enfants n’est réel et que total est égal à targetSum, renvoie true.
Empile chaque enfant réel c sous la forme (c, total + tree[c]).
Quand la pile est vide, renvoie 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

Comparer la somme à chaque nœud. Dans le deuxième exemple, 3 + 9 = 12 correspond au nœud 9, qui a un enfant, donc la réponse est false.
Laisser un emplacement enfant vide mettre fin à un chemin. Ainsi, le 9 du deuxième exemple met fin à un chemin passant par son emplacement gauche vide.
Oublier le cas où il n’y a que la racine. Un nœud unique est une feuille, donc [4] avec la cible 4 donne true, tout comme [0] avec la cible 0.
Lire au-delà de la fin du tableau. Une feuille située près de la fin peut avoir des index d’enfants qui dépassent la dernière entrée.
Confondre le décalage en Lua et en R. Gardez les index des nœuds à base 0 pour 2*i+1 et lisez tree[i + 1].

Questions fréquentes3

Quelle est la complexité temporelle de Path Sum ?

O(n) : chaque nœud est visité au plus une fois, 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é, sous forme de cadres d’appel ou d’entrées dans votre propre pile.

Peut-on résoudre Path Sum avec BFS ?

Oui. Place les paires composées d’un nœud et de la somme du chemin correspondant dans une file plutôt que dans une pile, et vérifie chaque feuille à sa sortie. La complexité temporelle 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. La copie des chemins peut coûter plus cher que le parcours lorsque de nombreuses feuilles correspondent.

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

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu

true