Leetcode für die Durchquerung der Ordnung auf Binärbaumebene

Geben Sie anhand der Wurzel eines Binärbaums die Durchquerung der Ebenenreihenfolge der Werte seiner Knoten zurück. (d. h. von links nach rechts, Ebene für Ebene).

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: []

Python-Lösung zur Traversierung auf binärer Baumebene

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

In dieser Lösung verwendetes Codierungsmuster

Das in allen bereitgestellten Implementierungen verwendete Codierungsmuster ist Tree Breadth-First Search (BFS).
Dieses Muster durchläuft üblicherweise einen Baum Ebene für Ebene und verarbeitet alle Knoten in der aktuellen Tiefe, bevor zur nächsten Tiefe übergegangen wird.
BFS wird mithilfe einer Warteschlangendatenstruktur implementiert, um die Knoten auf jeder Ebene zu verfolgen.

Zeit- und Raumkomplexität für diese Lösung

1. Die Zeitkomplexität ist O(N), da jeder Knoten einmal besucht wird.
2. Die Space-Komplexität beträgt O(M), da die Warteschlange (oder der Rekursionsstapel) die maximale Anzahl von Knoten auf jeder Ebene fasst.

Referenz:

1. LeetCode-Problem
2. LeetCode-Lösung
3. Breitensuche

Das obige ist der detaillierte Inhalt vonLeetcode für die Durchquerung der Ordnung auf Binärbaumebene. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!