Let Code Day8 À partir de zéro "1302. Somme des feuilles les plus profondes"

Aperçu

Il semble que des tests de codage soient menés à l'étranger lors d'entretiens d'ingénieurs, et dans de nombreux cas, l'essentiel est d'implémenter des fonctions et des classes spécifiques en fonction du thème.

En guise de contre-mesure, il semble qu'un site appelé Let Code prendra des mesures.

Un site qui forme une puissance algorithmique capable de résister aux tests de codage dont on parle très tôt.

Je pense qu'il vaut mieux avoir la puissance de l'algorithme d'un être humain, donc je vais résoudre le problème de manière irrégulière et écrire la méthode que j'ai pensé à ce moment-là sous forme de mémo.

Leetcode

En gros, je voudrais résoudre l'acceptation facile par ordre décroissant.

Dernière fois Leet Code Day7 à partir de zéro "104. Profondeur maximale de l'arbre binaire"

problème

1302. Deepest Leaves Sum

Ceci est le premier support. Ce problème a également beaucoup de bien, alors j'ai pensé que c'était un bon problème, alors je l'ai résolu.

Le problème est très simple, et étant donné un arbre dichotomisé, il renvoie la valeur totale des feuilles les plus profondes. ~~ Je pense qu'il y a de nombreux problèmes liés aux arbres ces jours-ci ... ~~ Un exemple est le suivant Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8] Output: 15

Dans ce cas, les feuilles les plus profondes sont 7 et 8, alors ajoutez jusqu'à 15.

1483_ex1.png

À première vue sur le problème, j'ai pensé que ce serait une idée simple d'utiliser une recherche prioritaire en profondeur pour vérifier la profondeur de toutes les feuilles et renvoyer la profondeur et la valeur. Cependant, j'ai senti que ce serait un peu de code redondant, et si vous utilisez une table de hachage en même temps lors de la vérification de la profondeur, vous pouvez conserver à la fois la profondeur et la valeur et l'écrire efficacement? Je l'ai pensé et mis en œuvre.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        ans = {}
        count = 0
        self.dfs(root,ans,count)
        
        return ans[max(ans)]
        
    def dfs(self,node,ans,count):
        if node:
            if node.left:
                self.dfs(node.left,ans,count+1)
            if node.right:
                self.dfs(node.right,ans,count+1)
        if count not in ans:
            ans[count] = node.val
        else:
            ans[count] += node.val
# Runtime: 104 ms, faster than 46.02% of Python3 online submissions for Deepest Leaves Sum.
# Memory Usage: 17.4 MB, less than 100.00% of Python3 online submissions for Deepest Leaves Sum.

Dans la fonction dfs, s'il est égal à l'indice de count, il est ajouté, sinon, la valeur est affectée telle quelle. Si vous renvoyez la valeur maximale en ans, la valeur de la feuille la plus profonde sera renvoyée à la fin. Mais cette réponse n'est pas très rapide ...

Je pense que les réponses suivantes sont les plus rapides en Python dans le domaine de l'observation.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root):
        q = [root]
        while q:
            pre, q = q, [child for p in q for child in [p.left, p.right] if child]
        return sum(node.val for node in pre)
# Runtime: 84 ms, faster than 98.04% of Python3 online submissions for Deepest Leaves Sum.
# Memory Usage: 17.3 MB, less than 100.00% of Python3 online submissions for Deepest Leaves Sum.

Mais c'est vraiment rapide ... Je ne pense pas pouvoir écrire un tel code pour le moment, mais c'est très intéressant de pouvoir lire un tel code.

Cela l'a rendu si rapide! Si vous avez un exemple, j'apprécierais que vous me disiez ce que vous avez conçu en écrivant le code, la consommation de mémoire et le temps d'exécution dans la section des commentaires.

Recommended Posts

Let Code Day8 À partir de zéro "1302. Somme des feuilles les plus profondes"
Soit Code Day75 à partir de zéro "15.3 Sum"
Let Code Day 39 "494. Target Sum" à partir de zéro
Let Code Day 33 "1. Two Sum" à partir de zéro
Let Code Day 32 "437. Path Sum III" à partir de zéro
Let Code Day 29 "46. Permutations" à partir de zéro
Soit Code Day 65 "560. Subarray Sum Equals K" à partir de zéro
Soit Code Day4 à partir de zéro "938. Range Sum of BST"
Let Code Day 27 "101. Symmetric Tree" à partir de zéro
Let Code Day 41 "394. Decode String" à partir de zéro
Let Code Day 25 "70. Grimper les escaliers" à partir de zéro
Laissez Code Day69 à partir de zéro "279. Perfect Squares"
Let Code Day 34 à partir de zéro "118. Le triangle de Pascal"
Laissez Code Day85 à partir de zéro "6. Conversion en zigzag"
Laissez Code Day20 partir de zéro "134. Station-service"
Let Code Day 88 "139. Word Break" à partir de zéro
Let Code Day 28 "198. House Robber" à partir de zéro
Let Code Day 36 "155. Min Stack" à partir de zéro
Let Code Day 17 "169. Majority Element" à partir de zéro
Let Code Day 23 "226. Invert Binary Tree" en partant de zéro
Soit Code Jour 22 à partir de zéro "141. Cycle de liste liée"
Let Code Day 30 à partir de zéro "234. Palindrome Linked List"
Soit Code Day68 à partir de zéro "709. To Lower Case"
Let Code Day 26 à partir de zéro "94. Traversée en ordre de l'arbre binaire"
Soit Code Day 46 à partir de zéro "406. Reconstruction de file d'attente par hauteur"
Let Code Day 31 "581. Le sous-tableau continu non trié le plus court" à partir de zéro
Let Code Day 38 à partir de zéro "208. Implémenter Trie (Prefix Tree)"
Soit Code Day3 à partir de zéro "1313. Decompress Run-Length Encoded List"
Let Code Day56 À partir de zéro "5453. Somme exécutée de 1d Array"
Let Code Day 77 "1502. Peut faire une progression arithmétique à partir de la séquence" à partir de zéro
Soit Code Jour 76 à partir de zéro "3. Sous-chaîne la plus longue sans caractères répétitifs"
Soit Code Day58 à partir de zéro "20. Parenthèses valides"
Soit Code Day16 à partir de zéro "344. Reverse String"
Soit Code Day49 à partir de zéro "1323. Maximum 69 Number"
Let Code Day89 "62. Chemins uniques" à partir de zéro
Let Code Day 55 "22. Générer des parenthèses" à partir de zéro
Soit Code Day18 à partir de zéro "53. Maximum Subarray"
Let Code Day 13 "338. Comptage des bits" à partir de zéro
Let Code Day71 À partir de zéro "1496. Traversée de chemin"
Let Code Day 61 "7. Integer Integer" à partir de zéro
Let Code Day 82 "392. Is Subsequence" Partant de zéro
Let Code Day51 "647. Sous-chaînes palindromiques" à partir de zéro
Let Code Day 50 "739. Températures quotidiennes" à partir de zéro
Let Code Day 15 "283. Move Zeroes" à partir de zéro
Soit Code Day14 à partir de zéro "136. Numéro unique"
Let Code Day 9 "701. Insérer dans un arbre de recherche binaire" à partir de zéro
Let Code Day 80 "703. Kth plus grand élément d'un flux" à partir de zéro
Let Code Day 66 "438. Find All Anagrams in a String" en partant de zéro
Let Code Day 11 À partir de zéro "1315. Somme des nœuds avec un grand-parent pair"
Let Code Day 43 à partir de zéro "5. Le plus long substrat palindromique"
Soit Code Day74 à partir de zéro "12. Integer to Roman"
Let Code Day 42 "2. Add Two Numbers" en partant de zéro
Let Code Day57 À partir de zéro "35. Rechercher Insérer la position"
Soit Code Day47 à partir de zéro "14. Préfixe commun le plus long"
Soit Code Day78 à partir de zéro "206. Liste liée inversée"
Let Code Day 90 à partir de zéro "101 1. Capacité à expédier les colis dans les D jours"
Soit Code Day 44 "543. Diamètre de l'arbre binaire" à partir de zéro
Soit Code Jour 64 à partir de zéro "287. Trouver le numéro en double"
Soit Code Jour 84 à partir de zéro "142. Cycle de liste liée II"
Let Code Day24 À partir de zéro "21. Fusionner deux listes triées"
Laissez Code Day12 partir de zéro "617. Fusionner deux arbres binaires"