? ?

1. 輸入檢查：

   if not root:return []

   • 如果根節點為空，直接返回空列表

2. 初始化：

   result = []
   queue = collections.deque([root])

   • result用于存儲最終結果
   • queue初始化包含根節點，使用雙端隊列實現

3. 主循環：

   while queue:level_size = len(queue)level = []

   • 當隊列不為空時繼續處理
   • level_size記錄當前層的節點數量
   • level用于存儲當前層的節點值

4. 處理當前層：

   for _ in range(level_size):node = queue.popleft()level.append(node.val)

   • 處理當前層的每個節點
   • 從隊列左側取出節點
   • 將節點值加入當前層列表

5. 處理子節點：

   for child in node.children:queue.append(child)

   • 將當前節點的所有子節點加入隊列（下一層）

6. 存儲當前層結果：

   result.append(level)

   • 將當前層的值列表加入最終結果

7. 返回結果：

   return result

   • 返回層次遍歷結果

具體例子

考慮以下N叉樹：

節點結構

• 節點1：值=1，children=[3,2,4]
• 節點3：值=3，children=[5,6]
• 節點2：值=2，children=[]
• 節點4：值=4，children=[]
• 節點5：值=5，children=[]
• 節點6：值=6，children=[]

代碼執行步驟

1. 初始化:

   • result = []
   • queue = [1]?(根節點)

2. 第一輪循環:

   • level_size = 1 (隊列中只有節點1)
   • level = []
   • 取出節點1，level = [1]
   • 將節點1的子節點(3,2,4)加入隊列: queue = [3,2,4]
   • result =[ [1] ]

3. 第二輪循環:

   • level_size = 3 (隊列中有3,2,4)
   • level = []
   • 取出節點3，level = [3]
   • 將節點3的子節點(5,6)加入隊列: queue = [2,4,5,6]
   • 取出節點2，level = [3,2]
   • 節點2沒有子節點
   • 取出節點4，level = [3,2,4]
   • 節點4沒有子節點
   • queue = [5,6]
   • result = [[1], [3,2,4]]

4. 第三輪循環:

   • level_size = 2 (隊列中有5,6)
   • level = []
   • 取出節點5，level = [5]
   • 節點5沒有子節點
   • 取出節點6，level = [5,6]
   • 節點6沒有子節點
   • queue = []
   • result = [[1], [3,2,4], [5,6]]

5. 循環結束:

   • 隊列為空，退出循環
   • 返回最終結果: [[1], [3,2,4], [5,6]]

最終輸出

這個層次遍歷的輸出結果是：

[ [1], [3,2,4], [5,6] ]

這個結果表示：

• 第一層(根層): 只有節點1
• 第二層: 節點3,2,4
• 第三層: 節點5,6

1. 初始狀態：
   • queue?=?[1]
   • result?=?[]

2. 第一層處理：

   • level_size?=?1
   • 處理節點1：
     • level?=?[1]
     • 加入子節點3,2,4?→?queue?=?[3,2,4]
   • result?=[ [1] ]

3. 第二層處理：

   • level_size?=?3
   • 處理節點3：
     • level?=?[3]
     • 加入子節點5,6?→?queue?=?[2,4,5,6]
   • 處理節點2：
     • level?=?[3,2]
     • 無子節點?→?queue?=?[4,5,6]
   • 處理節點4：
     • level?=