二元樹層次順序遍歷 Leetcode

給定二元樹的根，傳回其節點值的層級順序遍歷。 （即由左至右，逐級）。

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解決方案

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

本解決方案中使用的編碼模式

所有提供的實作中所使用的編碼模式是樹廣度優先搜尋（BFS）。
此模式通常逐層遍歷樹，在移動到下一個深度之前處理當前深度的所有節點。
BFS 使用佇列資料結構來實現，以追蹤每個層級的節點。

此解決方案的時間和空間複雜度

1. 時間複雜度為 O(N)，因為每個節點都被訪問一次。
2. 空間複雜度為 O(M)，因為佇列（或遞歸堆疊）在任何層級都能容納最大數量的節點。

參考：

1. LeetCode 問題
2. LeetCode 解決方案
3. 廣度優先搜尋

以上是二元樹層次順序遍歷 Leetcode的詳細內容。更多資訊請關注PHP中文網其他相關文章！