🔗 二叉树的层序遍历

题目来源：102. 二叉树的层序遍历 – 力扣（LeetCode）

📌 题目描述

给你二叉树的根节点 root，返回其节点值的 层序遍历。
（即逐层地，从左到右访问所有节点，每一层的结果单独作为一个列表。）

✅ 示例解析

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
解释：

• 第 0 层：[3]
• 第 1 层：[9, 20]
• 第 2 层：[15, 7]

示例 2：

输入：root = [1]
输出：“

示例 3：

输入：root = []
输出：[]
解释：空树无节点，返回空列表。

⚠️ 提示

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

💡 解法：广度优先搜索（BFS） + 队列 —— O(n) 时间，O(w) 空间

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> currentLevel = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll(); 
                currentLevel.add(node.val);

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            result.add(currentLevel);
        }

        return result;
    }
}

📊 复杂度分析

• 时间复杂度：O(n)
  每个节点恰好入队和出队一次，总操作次数为 O(n)。
• 空间复杂度：O(w)
  w 是树的最大宽度（即某一层最多节点数）。队列中最多同时存储一层的所有节点。最坏情况下（完全二叉树最后一层），w ≈ n/2，因此空间复杂度为 O(n)；但通常表述为 O(w) 更准确。

🧩 解题思路

核心思想：广度优先遍历（BFS）
层序遍历是 BFS 在二叉树中的标准应用。

关键技巧：按层处理

• 每次进入 while 循环时，队列中恰好包含当前层的所有节点。
• 通过 int size = queue.size() 固定当前层的节点数量，确保 for 循环只处理这一层，避免与下一层混淆。