vvrf / DSA.log

问题拆解

从上到下逐层遍历二叉树，同一层的节点放进同一个子数组。

BFS 用队列做是自然的：根入队，然后不断弹出节点、把它的孩子入队，弹出顺序正好是逐层从左到右。但朴素 BFS 吐出的是一条扁平序列，节点之间没有“层”的边界。给节点附带深度信息可以解决，不过有个更干净的观察：在处理某一层的第一个节点之前，队列里装的恰好是这一层的全部节点——上一层已全部弹出，下一层还没进来。

每轮循环开始时先记下 size = 队列长度，然后恰好弹出 size 个节点，它们就是完整的一层；弹出过程中入队的孩子留给下一轮。

关键在于必须把 size 存进变量：弹出孩子入队时队列长度在实时变化，若循环条件里直接写 queue.size()，层的边界就被冲掉了。

队列按层弹出

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size(); // 定格当前层的节点数
        List<Integer> level = new ArrayList<>(size);
        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);
        }
        res.add(level);
    }
    return res;
}

from collections import deque

def levelOrder(root):
    if not root:
        return []
    res = []
    queue = deque([root])
    while queue:
        size = len(queue)  # 定格当前层的节点数
        level = []
        for _ in range(size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(level)
    return res

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    res := [][]int{}
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        size := len(queue) // 定格当前层的节点数
        level := make([]int, 0, size)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        res = append(res, level)
    }
    return res
}

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
    let mut res = Vec::new();
    let mut queue = VecDeque::new();
    if let Some(node) = root {
        queue.push_back(node);
    }
    while !queue.is_empty() {
        let size = queue.len(); // 定格当前层的节点数
        let mut level = Vec::with_capacity(size);
        for _ in 0..size {
            let node = queue.pop_front().unwrap();
            let node = node.borrow();
            level.push(node.val);
            if let Some(left) = node.left.clone() {
                queue.push_back(left);
            }
            if let Some(right) = node.right.clone() {
                queue.push_back(right);
            }
        }
        res.push(level);
    }
    res
}

外层 while 走一次是一层，内层 for 精确弹出 size 个节点——这两层循环的分工就是整个算法。Go 版用切片模拟队列，queue = queue[1:] 弹头部虽不释放底层数组，但树遍历的规模下无妨；Rust 版用 VecDeque，注意孩子指针要 clone() 一份 Rc 再入队，因为 borrow() 出来的引用不能带出作用域。

复杂度

指标	复杂度	原因
时间	`O(n)`	每个节点入队、出队各一次
空间	`O(n)`	队列最宽时装下一整层，最坏约 n/2 个节点

可以迁移的模式

“先定格 size 再弹 size 个”是 BFS 按层处理的通用骨架，改动收集逻辑就能做锯齿形遍历（103）、右视图（199）、每层最大值（515）；
需要“逐层”语义时不必给节点挂深度标签，队列在层与层之间的瞬时快照就是分界；
求最短步数/最少轮数的题（如 542、994），层数本身就是答案，同一副骨架直接复用。

层序遍历是所有 BFS 变体题的母版，把这个双层循环写熟，剩下的只是换收集方式。