題目
#

leetcode 102 - Binary Tree Level Order Traversal (題目說明請點連結)

題目簡述
#

給一個二元樹的根節點 root，返回其節點值的層序遍歷（從上到下按層級遍歷）。
層序遍歷：從根節點開始，逐層遍歷，每一層從左到右遍歷節點。

範例
#

Example 1:

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

graph TD; A[3] B[9] C[20] D[null] E[null] F[15] G[7] A --> B A --> C B --> D B --> E C --> F C --> G

Example 2:

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

解題思路
#

這題要求我們對二元樹進行層序遍歷。我們可以使用廣度優先搜尋（BFS）來解決這個問題，通過使用佇列（Queue）來維護每一層的節點，並逐層處理。

解法
#

BFS

創建一個結果列表和一個佇列
將根節點加入佇列
當佇列不為空時，進行以下操作：
- 記錄當前層級的節點數量
- 遍歷當前層級的所有節點
- 將節點值加入當前層級列表
- 將子節點加入佇列
將當前層級列表加入結果列表
返回結果

步驟
#

初始化：
- 創建結果列表 result 和佇列 queue
- 將根節點加入佇列
層序遍歷：
- 當佇列不為空時，記錄當前層級大小
- 遍歷當前層級的所有節點
- 將節點值加入層級列表
- 將非空的子節點加入佇列
返回結果：
- 將每層的節點值列表加入結果列表

例子說明
#

root = [3,9,20,null,null,15,7]

graph TD; A[3] B[9] C[20] D[null] E[null] F[15] G[7] A --> B A --> C B --> D B --> E C --> F C --> G

步驟	佇列狀態	當前層級	層級列表	結果
初始化	`[3]`	1	[]	`[]`
第 1 層	`[9,20]`	1	`[3]`	`[[3]]`
第 2 層	`[15,7]`	2	`[9,20]`	`[[3],[9,20]]`
第 3 層	`[]`	2	`[15,7]`	`[[3],[9,20],[15,7]]`

最終結果： [[3],[9,20],[15,7]]

層序遍歷說明：

第 1 層：根節點 3
第 2 層：左子節點 9，右子節點 20
第 3 層：節點 20 的左子節點 15，右子節點 7

完整程式碼
#

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        
        // 邊界檢查：如果根節點為空，返回空列表
        if (root == null) {
            return result;
        }

        // 創建佇列用於廣度優先搜尋
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        // 當佇列不為空時，繼續遍歷
        while (!queue.isEmpty()) {
            // 記錄當前層級的節點數量
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            
            // 遍歷當前層級的所有節點
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();

                // 將當前節點值加入層級列表
                level.add(node.val);

                // 將左子節點加入佇列（如果存在）
                if (node.left != null) {
                    queue.offer(node.left);
                }
                // 將右子節點加入佇列（如果存在）
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            
            // 將當前層級列表加入結果列表
            result.add(level);
        }

        return result;
    }
}