[PYTHON] Lassen Sie Code Day7 ab Null "104. Maximale Tiefe des Binärbaums"

Ü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 Day6 ab Null "1342. Anzahl der Schritte zum Reduzieren einer Zahl auf Null"

Es dauerte eine Woche ohne zu überspringen. Herzliche Glückwünsche.

Problem

104. Maximum Depth of Binary Tree

Es ist ein ziemlich frühes Problem, aber ich fand es ein gutes Problem, die Struktur der Dichotomien zu verstehen.

Bei gegebenen Dichotomien werden Sie aufgefordert, einen Algorithmus zu schreiben, der den Maximalwert für diese Tiefe ermittelt.

example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
return its depth = 3.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        depth = 0
        stack = [(root,1)]
        
        while stack:
            root,length = stack.pop()
            if not root:
                return 0
            
            if length > depth:
                depth = length
            if root.right:
                stack.append((root.right,length + 1))
            if root.left:
                stack.append((root.left,length + 1))
        return depth
# Runtime: 40 ms, faster than 70.51% of Python3 online submissions for Maximum Depth of Binary Tree.
# Memory Usage: 14.9 MB, less than 90.62% of Python3 online submissions for Maximum Depth of Binary Tree.

Das Problem mit dem vorherigen Dichotomiebaum, Leet Code Day 4 "938. Range Sum of BST" ab Null Sah.

Ich habe es herausgefunden, indem ich es bei Discuss usw. nachgeschlagen habe, aber es gibt auch eine solche Art zu schreiben.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from collections import deque

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        queue = deque([(root, 1)])
        while queue:
            curr, val = queue.popleft()
            if not curr.left and not curr.right and not queue:
                return val
            if curr.left:
                queue.append((curr.left, val+1))
            if curr.right:
                queue.append((curr.right, val+1))
# Runtime: 36 ms, faster than 89.87% of Python3 online submissions for Maximum Depth of Binary Tree.
# Memory Usage: 15 MB, less than 90.62% of Python3 online submissions for Maximum Depth of Binary Tree.

Es wird mit deque implementiert.

Deque ist eine Verallgemeinerung von Stapeln und Warteschlangen (der Name wird "Deck" ausgesprochen, was eine Abkürzung für "Double-Ended Queue" ist). Deques können von beiden Seiten angehängt und eingefügt werden, sind threadsicher und speichereffizient und können aus beiden Richtungen mit einer Leistung von ungefähr O (1) ausgeführt werden.

Es ist so schnell wie es sich anhört. Tatsächlich ist Runtime auch schneller als andere Antworten.