[PYTHON] Let Code Day 26 à partir de zéro "94. Traversée en ordre 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 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

Table de codes Leet commençant à zéro

Dernière fois Leet Code Day 25 "70. Climbing Stairs" à partir de zéro

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

Twitter Je le fais.

problème

543. Diameter of Binary Tree Le niveau de difficulté est facile. Extrait des 100 questions les plus appréciées.

Étant donné un arbre dichotomisé, renvoyez le diamètre de cet arbre. Le diamètre se réfère ici au passage qui va et vient sur la plus longue distance entre chaque nœud.

Example:

Example:
Given a binary tree
          1
         / \
        2   3
       / \     
      4   5    
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

Dans ce cas, le plus long est de 4 à 3 et de 5 à 3, et le nombre de branches entre les deux est de 3, donc 3 est renvoyé.

Solution

C'était une recherche prioritaire en profondeur.

# 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 diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.ans = 0
        
        def dfs(node):
            if not node:
                return 0
            right = dfs(node.right)
            left = dfs(node.left)
            self.ans = max(self.ans,left+right)
            return max(left,right) + 1
    
        dfs(root)
        return self.ans
# Runtime: 44 ms, faster than 72.73% of Python3 online submissions for Diameter of Binary Tree.
# Memory Usage: 15.9 MB, less than 51.72% of Python3 online submissions for Diameter of Binary Tree.

Le flux de base est le même que celui de la recherche de priorité de profondeur générale. Cependant, comme il est nécessaire de vérifier la durée cette fois, j'ai préparé une variable ʻans` à cet effet et ajouté un calcul.

Même avec les problèmes d'arbres dans le passé, je n'écris que des recherches à priorité de profondeur, donc je pense que je devrais bientôt étudier les recherches à priorité de largeur. Il est trop tard aujourd'hui, alors c'est tout, merci.

S'il y a une autre bonne réponse, je l'ajouterai.