二叉树层序遍历：思路拆解与 Java 实现

二叉树层序遍历

二叉树的层序遍历要求我们'从上到下、从左到右'地访问所有节点，并将结果按层级组织成二维列表。这是面试中非常经典的广度优先搜索（BFS）应用场景。

核心思路

要实现分层输出，关键在于如何区分每一层的节点。队列（Queue）天然符合'先进先出'的特性，非常适合这种场景。配合一个记录当前层节点数量的变量，就能精准控制循环边界。

初始化与边界处理

首先准备一个二维列表用来存放最终结果。拿到根节点后，如果它是空的，直接返回空列表即可，避免后续空指针异常。

List<List<Character>> ret = new ArrayList<>();
if (root == null) {
    return ret;
}

队列辅助与分层逻辑

创建一个队列，将根节点入队。接下来是核心循环：

1. 外层循环：只要队列不为空，说明还有节点需要处理。
2. 内层循环：这是分层的关键。在每次进入外层循环时，先获取当前队列的大小 size。这个数值代表了当前这一层有多少个节点。
3. 接着循环 size 次：依次取出节点加入当前层列表，并将其左右子节点（如果不为空）加入队列。

通过固定 size，我们确保了内层循环只处理当前层的节点，下一层的节点会被暂存到队列末尾，留待下一次外层循环处理。

完整代码实现

下面是完整的 Java 实现，包含了必要的注释说明关键步骤。

public List<List<Character>> levelOrder(TreeNode root) {
    // 创建二维数组列表：储存每层节点
    List<List<Character>> ret = new ArrayList<>();
    
    // 空树处理
    if (root == null) {
        return ret;
    }
    
    // 创建队列
    Queue<TreeNode> queue = new LinkedList<>();
    // 进队
    queue.offer(root);
    
    // 外层循环：处理每一层
    while (!queue.isEmpty()) {
        // 当前层存储列表
        List<Character> curRow = new ArrayList<>();
        // 当前层节点数
        int size = queue.size();
        
        
         (size != ) {
            
               queue.poll();
            
            curRow.add(cur.val);
            
             (cur.left != ) {
                queue.offer(cur.left);
            }
             (cur.right != ) {
                queue.offer(cur.right);
            }
            size--;
        }
        
        ret.add(curRow);
    }
     ret;
}