[PYTHON] Let Code Day7 À partir de zéro "104. Profondeur maximale de l'arbre binaire"

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 de mettre en œuvre 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 à des 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 Day6 à partir de zéro "1342. Nombre d'étapes pour réduire un nombre à zéro"

Cela a duré une semaine sans sauter. Toutes nos félicitations.

problème

104. Maximum Depth of Binary Tree

C'est un problème assez précoce, mais j'ai pensé que c'était un bon problème pour comprendre la structure des dichotomies.

Étant donné une dichotomie, il vous sera demandé d'écrire un algorithme qui trouve la valeur maximale pour cette profondeur.

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.

Le problème avec l'arbre de dichotomie précédent, Leet Code Day4 "938. Range Sum of BST" commençant à zéro Vu.

Je l'ai découvert en cherchant sur Discuss etc., mais il existe aussi une telle façon d'écrire.

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

Il est implémenté en utilisant deque.

Deque est une généralisation des piles et des files d'attente (le nom se prononce "deck", qui est une abréviation de "double-end queue"). Les Deques peuvent être ajoutés et pop de chaque côté, sont thread-safe et économes en mémoire, et peuvent fonctionner dans les deux sens avec des performances d'environ O (1).

C'est aussi rapide que ça en a l'air. En fait, Runtime est également plus rapide que les autres réponses.