[PYTHON] Lassen Sie Code Day8 ab Null "1302. Deepest Leaves Sum"

Überblick

Es scheint, dass Codierungstests in Ingenieurinterviews im Ausland durchgeführt werden, und in vielen Fällen besteht die Hauptsache darin, bestimmte Funktionen und Klassen entsprechend dem Thema zu implementieren.

Als Gegenmaßnahme scheint eine Website namens Let Code Maßnahmen zu ergreifen.

Eine Site, die algorithmische Leistung trainiert, die Codierungstests standhält, über die früh gesprochen wird.

Ich denke, es ist besser, die Algorithmuskraft eines Menschen zu haben, also werde ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.

Leetcode

Grundsätzlich möchte ich die einfache Akzeptanz in absteigender Reihenfolge lösen.

Letztes Mal Leet Code Day7 ab Null "104. Maximale Tiefe des Binärbaums"

Problem

1302. Deepest Leaves Sum

Dies ist das erste Medium. Dieses Problem hat auch viel Gutes, also dachte ich, es sei ein gutes Problem, also habe ich es gelöst.

Das Problem ist sehr einfach und gibt bei einem dichotomisierten Baum den Gesamtwert der tiefsten Blätter zurück. ~~ Ich habe das Gefühl, dass es heutzutage viele Probleme mit Bäumen gibt ... ~~ Ein Beispiel ist wie folgt Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8] Output: 15

In diesem Fall sind die tiefsten Blätter 7 und 8, also addieren Sie bis zu 15.

Auf den ersten Blick dachte ich, es wäre eine einfache Idee, eine Suche mit Tiefenpriorität zu verwenden, um die Tiefe aller Blätter zu überprüfen und die Tiefe und den Wert zurückzugeben. Ich hatte jedoch das Gefühl, dass es sich um einen etwas redundanten Code handelt. Wenn Sie beim Überprüfen der Tiefe gleichzeitig eine Hash-Tabelle verwenden, können Sie sowohl die Tiefe als auch den Wert halten und effizient schreiben. Ich habe es gedacht und umgesetzt.

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

Wenn es in der Funktion dfs gleich dem Zählindex ist, wird es hinzugefügt, andernfalls wird der Wert so zugewiesen, wie er ist. Wenn Sie den Maximalwert in ans zurückgeben, wird am Ende der Wert des tiefsten Blattes zurückgegeben. Aber diese Antwort ist nicht sehr schnell ...

Ich denke, die folgenden Antworten sind die schnellsten in Python im Bereich der Beobachtungsdiskussion.

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

Aber es ist sehr schnell ... Ich glaube nicht, dass ich solchen Code im Moment schreiben kann, aber es ist sehr interessant, solchen Code lesen zu können.

Das hat es so schnell gemacht! Wenn Sie ein Beispiel haben, würde ich es begrüßen, wenn Sie mir sagen könnten, was Sie sich ausgedacht haben, indem Sie den Code, den Speicherverbrauch und die Laufzeit in den Kommentarbereich geschrieben haben.