一、題目介紹
今天要解的題目是LeetCode的Binary Tree Level Order Traversal，中文可以稱為「二元樹的層序走訪」。

題目會給定一棵二元樹root，要求按照由上到下、由左到右的順序，逐層走訪樹中的節點。

例如：

按照Level Order Traversal的方式走訪
第一層：3
第二層：9, 20
第三層：15, 7

最後結果為[[3],[9, 20],[15, 7]]

與前一天的Inorder Traversal不同，這次不是沿著某一條分支一直深入，而是先處理目前這一層，再處理下一層。
因此這題適合使用BFS（Breadth-First Search，廣度優先搜尋）＋ Queue（佇列）

二、解題思路
BFS 的核心概念是：先處理距離起點較近的節點，再處理更深層的節點。

在Binary Tree中，就可以理解成
第 1 層
↓
第 2 層
↓
第 3 層
↓
第 4 層
要做到「一層一層處理」，可以使用Queue

Queue的特性是
FIFO
First In, First Out
先進先出

這和Day2的Stack正好相反
Stack：LIFO → 後進先出
Queue：FIFO → 先進先出

解題步驟

1. 如果root為空，直接回傳空結果。
2. 將root放入Queue。
3. 每次處理Queue目前的所有節點。
4. 將目前節點的值加入當前層的結果。
5. 如果目前節點有左子節點，就加入Queue。
6. 如果有右子節點，也加入Queue。
7. 當這一層全部處理完後，再處理下一層。
8. 重複直到Queue為空。

三、解題流程
以以下二元樹為例

一開始 Queue = [3]

Step1：處理第一層
取出3
目前節點：3
將3加入第一層結果：[3]
接著把3的左右子節點加入Queue
Queue = [9, 20]

Step2：處理第二層
目前Queue有[9, 20]
這代表目前需要處理第二層的兩個節點

先取出9
結果：[9]
9沒有子節點

接著取出20
結果：[9, 20]

20有左右子節點，因此加入Queue = [15, 7]
第二層完成：[9, 20]

Step3：處理第三層
Queue = [15, 7]
依序取出15, 7
得到[15, 7]
此時Queue已經沒有節點，代表整棵樹都走訪完成

最後結果[[3],[9, 20],[15, 7]]

四、Java實作

五、Python實作

六、時間與空間複雜度
Java

• 時間複雜度：O(n)
  • 每個節點都會被加入Queue一次，也會從Queue取出一次。
  • 因此如果樹中共有n個節點，每個節點只會被處理一次，所以時間複雜度為：O(n)
• 空間複雜度：O(n)
  • Queue最多可能存放一整層的節點。
  • 在最壞情況下，一棵二元樹可能有接近n個節點位於同一層，因此Queue可能需要O(n)的空間。
  • 另外，result本身也需要儲存所有節點的值，因此也需要O(n)空間。
  • 所以整體空間複雜度為：O(n)

Python

• 時間複雜度：O(n)
  • 每個節點都會被處理一次，因此時間複雜度為：O(n)
• 空間複雜度：O(n)
  • Queue 以及最後儲存所有走訪結果的result都需要額外空間，因此整體空間複雜度為：O(n)

七、Java與Python解法比較

八、實作結果
Leetcode測試結果：Accepted

九、今日學習心得
今天學習了Binary Tree Level Order Traversal，第一次將BFS（廣度優先搜尋）實際應用在二元樹上。

與Day11的Inorder Traversal相比，兩者最大的差別在於走訪方式。

Day11使用DFS，會沿著樹的分支深入：左 → 根 → 右

而今天的BFS則是：第一層 → 第二層 → 第三層

也就是一次處理同一層的節點。

今天也重新接觸到Queue的概念。Queue使用FIFO，也就是先進先出，這個特性非常適合BFS，因為先加入Queue的節點會先被處理，而它們的子節點則會排在後面，形成一層一層向下的走訪順序。

透過這題，我也更加理解DFS和BFS的差異。遇到Binary Tree的問題時，可以先思考題目需要的是「深入探索」還是「逐層處理」，再選擇適合的走訪方式。