Additionner les nombres racine à feuille dans un arbre binaire – Leetcode Solutions

Un problème de difficulté moyenne de Leetcode

Sum Root to Leaf Numbers est un problème intéressant de Leetcode. Le problème est de difficulté moyenne et concerne les arbres binaires. Ce message est une solution expliquée au problème.

Je suppose que vous connaissez Python et le concept d’arbres binaires. Sinon, vous pouvez lire Cet article pour commencer.

Étant donné un arbre binaire dont les nœuds contiennent des valeurs 0-9, nous devons trouver la somme de tous les nombres formés par les chemins de la racine à la feuille. Une feuille est un nœud qui n’a pas de nœuds enfants. Dans un arbre binaire, un chemin de la racine à la feuille est toujours unique. Voici ci-dessous le comportement attendu de la solution requise:

Dans l’arborescence de gauche, la sortie est 25. 25 est la somme de 12 et 13, qui sont les deux nombres formés à partir de 1 et visiter chaque feuille. Dans l’arborescence de droite, la sortie est 1026 car c’est la somme des trois nombres 495, 491 et 40.

1. Pour construire un nombre, nous traversons l’arbre de la racine à la feuille, en ajoutant des chiffres où le chiffre le plus significatif est à la racine et le chiffre le moins significatif est à la feuille. Nous visitons quelques feuilles avant d’autres nœuds plus proches de la racine. Cela suggère qu’une recherche en profondeur sera utile.
2. le construction des nombres est incrémentiel et similaire: la seule différence entre 495 et 491 (à partir de l’arbre de droite) est le dernier chiffre. Si nous supprimons le 5 et insérez un 1 à sa place, nous avons le prochain numéro requis. Un nombre comprend essentiellement le chiffre de la feuille ajouté à tous les chiffres des nœuds ancêtres. Ainsi, les nombres dans le même sous-arbre ont des chiffres communs.
3. Enfin, notez que ce problème implique un arbre, donc une solution récursive est utile.

On peut faire un pre-order traversée de l’arbre où nous construisons incrémentalement un nombre et exploitons le fait que les nombres formés par des nœuds dans le même sous-arbre ont des chiffres communs. Lorsque nous avons fini de former des nombres dans un sous-arbre, nous pouvons revenir en arrière et passer à un autre sous-arbre.

Créons un Solution pour englober notre solution.

La signature de méthode qui nous est donnée dans le problème a un argument: root, qui est du type TreeNode . UNE TreeNode est la suivante (à partir de Leetcode):

De l’observation n ° 2, notez que l’ajout du chiffre d’un nœud à ses ancêtres peut être réalisé en en mouvement tous les chiffres du nombre formé par les ancêtres à droite par 1 place et en ajoutant le chiffre du nœud actuel. Les chiffres peuvent être déplacé en multipliant le nombre formé par les ancêtres par 10 (puisque nous sommes en base 10). Par exemple:

495 = 49 x 10 + 5

Ainsi, nous pouvons garder une trace de la courant chiffres dans un entier. Ceci est important car nous n’engendrons pas d’espace de stockage supplémentaire pour les tailles d’entrée plus élevées. Nous pouvons passer cette valeur dans le paramètre de fonction lui-même. Étant donné que la signature de méthode donnée ne peut avoir qu’un seul paramètre, créons un sum_root_to_leaf_helper méthode.

On peut penser au sum_root_to_leaf_helper récursivement et traiter chaque nœud différemment selon qu’il s’agit ou non d’une feuille.

• Si le nœud est une feuille, nous voulons ajouter son chiffre à nos chiffres actuels en déplaçant tous les autres chiffres vers la droite. Nous voulons également renvoyer cette valeur (puisque nous allons revenir en arrière à partir d’ici).
• S’il ne s’agit pas d’une feuille, nous voulons ajouter le chiffre à nos chiffres actuels en déplaçant tous les autres chiffres vers la droite. Nous voulons également continuer à construire le nombre en parcourant les sous-arbres gauche et droit de ce nœud.

Si le nœud actuel est un None, nous pouvons simplement retourner 0 car cela ne compte pas.

Ainsi, notre sum_root_to_leaf_helper sera la suivante:

Nous utilisons une valeur par défaut pour que la somme partielle soit 0.

Dans notre méthode principale, nous voulons inclure le sum_root_to_leaf_helper comme méthode imbriquée et transmettez simplement le paramètre node. Enfin, voici à quoi ressemble notre solution:

Lorsque nous trouvons une solution, il est important d’analyser sa complexité algorithmique non seulement pour estimer ses performances mais aussi pour identifier les domaines à améliorer et réfléchir à nos compétences en résolution de problèmes. Nous devons toujours poser la question: pouvons-nous faire mieux que X? Où X est la complexité actuelle de notre solution.

Temps:

Notre solution est une modification de la traversée de pré-ordre de recherche en profondeur où nous visitons tous les nœuds une seule fois et effectuons un calcul trivial (déplacement des chiffres par multiplication d’entiers). Ainsi, notre runtime est simplement O(N) où N représente le nombre de nœuds dans l’arbre donné. Une solution meilleure que O(N) ne semble pas possible car pour construire un nombre à partir de chiffres, nous devons connaître tous les chiffres (et donc visiter tous les nœuds).

Espace:

En termes de stockage, nous encourons un coût élevé dans la pile d’appels de récursivité qui se constitue comme notre sum_root_to_leaf_helper s’appelle. Ces appels accumuler comme on attend un autre pour finir.

La pile d’appels maximale dépend de la hauteur de l’arbre binaire (puisque nous commençons à revenir en arrière après avoir visité une feuille), ce qui donne une complexité de O(H) où H est la hauteur de l’arbre binaire. Dans le pire des cas, l’arbre binaire est biaisé dans les deux sens et donc H = N. Par conséquent, la complexité spatiale la plus défavorable est O(N).

Tu peux lire Cet article pour en savoir plus sur les piles d’appels de récursivité.

Il est possible de faire mieux que O(N) en utilisant un Morris Preorder Traversal. L’idée de base est de lier temporairement un nœud et son prédécesseur. Vous pouvez en savoir plus à ce sujet ici.

J’espère que ce message a aidé! Veuillez me faire savoir si vous avez des commentaires, des commentaires ou des suggestions en répondant à ce message.

Advay, Kevin, Louie pour avoir relu ce post et Yangshun pour l’idée de l’ajouter en tant que blog.