力扣刷题之102、二叉树的层序遍历
题目难度：中等
标签：树、广度优先搜索（BFS）、二叉树
题目描述
给你二叉树的根节点root，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。
示例：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
输入：root = [1]
输出：``
输入：root = []
输出：[]
解题思路
层序遍历是广度优先搜索（BFS）在二叉树中的典型应用。与深度优先搜索（DFS）不同，BFS 按“层”处理节点，非常适合用队列（Queue）来实现。
核心思想：
- 使用队列存储待访问的节点。
- 每次处理当前层的所有节点（通过记录当前队列大小）。
- 将当前层节点值存入一个列表，再将该列表加入最终结果。
- 同时把下一层的左右子节点加入队列，为下一轮做准备。
关键点：不能直接用
queue.size()作为 for 循环条件，因为队列在循环中会动态变化。必须提前保存当前层的节点数量！
代码实现（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; * } * } */classSolution{publicList<List<Integer>>levelOrder(TreeNoderoot){//创建结果列表，用于存储每一次的节点值List<List<Integer>>result=newArrayList<>();//边界情况：如果根节点为空，直接返回空列表if(root==null){returnresult;}//创建队列，用于BFS的起点Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);//当队列不为空时，继续处理while(!queue.isEmpty()){//获取当前层的节点数量intlevelsize=queue.size();//创建列表存储当前层的所有节点值List<Integer>current=newArrayList<>();//处理当前层的所有节点for(inti=0;i<levelsize;i++){//从队列头部取出一个节点TreeNodeNode=queue.poll();//将当前节点的值添加到当前层的结果列表current.add(Node.val);//如果左子节点存在，将其加入到队列中if(Node.left!=null){queue.offer(Node.left);}//如果右子节点存在，将其加入到队列中if(Node.right!=null){queue.offer(Node.right);}}//将当前层的结果添加到最终结果列表中result.add(current);}//返回层序遍历的结果returnresult;}}复杂度分析
时间复杂度：
O(n)
每个节点被访问一次，n 为树中节点总数。空间复杂度：
O(n)
最坏情况下（完全二叉树），队列中最多存储约 n/2 个节点（最后一层）。
总结
层序遍历是树类问题的基础技能，掌握 BFS + 队列的写法，能轻松应对一大类“按层处理”的题目。所以要记住：先记录当前层大小，再循环处理，这是避免逻辑错误的关键！
)
