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.

Apparemment, de nombreux ingénieurs prennent des mesures sur le site appelé LetCode.

C'est un site qui forme la puissance de l'algorithme qui peut résister au test de codage qui est effectué au début, et c'est un chemin inévitable pour ceux qui veulent faire carrière dans une entreprise de technologie à l'étranger.

Je l'ai écrit en grand, mais je n'ai pas l'intention d'avoir une telle interview pour le moment.

Cependant, en tant qu'ingénieur informatique, il serait préférable d'avoir le même niveau de puissance d'algorithme qu'une personne, alors j'aimerais résoudre le problème de manière irrégulière et écrire la méthode que je pensais à ce moment-là sous forme de mémo.

Leetcode

Je le résolve avec Python3.

Table de codes Leet commençant à zéro

Dernière fois Leet Code Day 82 "392. Is Subsequence" partant de zéro

Twitter Je le fais.

** Blog technique Commencé! !! ** ** Je pense que la technologie écrira sur LetCode, Django, Nuxt, etc. ** C'est plus rapide à mettre à jour **, merci pour votre coopération!

problème

102. Binary Tree Level Order Traversal Le niveau de difficulté est moyen. C'est un extrait de la collection de problèmes comme avant.

Le problème est, étant donné un arbre binaire, de concevoir un algorithme qui renvoie une liste de valeurs égales à côté de l'ordre hiérarchique des valeurs pour ce nœud. (C'est-à-dire de gauche à droite, niveau par niveau).

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

Un exemple est comme ça. J'espère que tu comprends ce que je veux dire.

Solution

Je l'ai résolu avec DFS.

# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
        ans,level = [],0
        self.dfs(root,level,ans)
        return ans
    
    def dfs(self,root,level,ans):
        if not root:
            return
        if len(ans) < level+1:
            ans.append([])
        ans[level].append(root.val)
        self.dfs(root.left,level+1,ans)
        self.dfs(root.right,level+1,ans)
# Runtime: 32 ms, faster than 86.02% of Python3 online submissions for Binary Tree Level Order Traversal.
# Memory Usage: 14.2 MB, less than 43.09% of Python3 online submissions for Binary Tree Level Order Traversal.

C'est un simple DFS. Puisqu'il est décidé de le renvoyer sous forme de liste, si vous augmentez la longueur de la liste, vous pouvez bien couvrir les éléments de la hiérarchie.

Cette fois, je l'ai résolu avec la recherche de priorité en profondeur à laquelle je suis habitué, mais il existe des exemples de résolution avec BFS et des réponses à l'aide de files d'attente dans la discussion, il semble donc que la solution préférée d'un individu apparaîtra. C'est un problème.

Alors c'est tout pour cette fois. Je vous remercie pour votre travail acharné.

[PYTHON] Let Code Day83 À partir de zéro "102. Traversée de l'ordre au niveau de l'arborescence binaire"

Aperçu

problème

Solution