力扣刷题之102、二叉树的层序遍历

力扣刷题之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 + 队列的写法，能轻松应对一大类“按层处理”的题目。所以要记住：先记录当前层大小，再循环处理，这是避免逻辑错误的关键！