[PYTHON] 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.

À 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.