Traversée d'ordre au niveau de l'arbre binaire Leetcode

Étant donné la racine d'un arbre binaire, renvoie l'ordre de parcours des valeurs de ses nœuds. (c'est-à-dire de gauche à droite, niveau par niveau).

Example 1:
Input: root = [3,9,20,null,null,15,7] 
Output: [[3],[9,20],[15,7]]

Example 2:
Input: root = [1]
Output: [[1]]

Example 3:
Input: root = []
Output: []

Solution Python de traversée d'ordre au niveau de l'arbre binaire

class Solution(object):
    def levelOrder(self, root):
        if not root:
            return []
        Q = deque([root])
        levels = [[root.val]]
        temp = deque()
        while Q:
            node = Q.popleft()
            if node.left: temp.append(node.left)
            if node.right: temp.append(node.right)
            if not Q:
                if temp:
                    levels.append([n.val for n in temp])
                Q = temp
                temp = deque()
        return levels

Modèle de codage utilisé dans cette solution

Le modèle de codage utilisé dans toutes les implémentations fournies est Tree Breadth-First Search (BFS).
Ce modèle traverse généralement une arborescence niveau par niveau, traitant tous les nœuds à la profondeur actuelle avant de passer à la profondeur suivante.
BFS est implémenté à l'aide d'une structure de données de file d'attente pour suivre les nœuds à chaque niveau.

Complexité temporelle et spatiale pour cette solution

1. La complexité temporelle est O(N) car chaque nœud est visité une fois.
2. La complexité spatiale est O(M) car la file d'attente (ou pile de récursion) peut contenir jusqu'au nombre maximum de nœuds à n'importe quel niveau.

Référence :

1. Problème LeetCode
2. Solution LeetCode
3. Recherche en largeur d'abord

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!