跳至主要內容

二叉树层序遍历——BFS队列模板与变体10题

老张2026/4/30大约 8 分钟

二叉树层序遍历——BFS队列模板与变体10题

适读人群：Java 后端工程师、准备算法面试的同学 | 阅读时长：约25分钟 | 难度：Medium

开篇故事

如果让我选一个"投入产出比最高"的算法知识点，我会毫不犹豫地说：二叉树的 BFS 层序遍历。

这个模板我研究了一遍之后，连续解决了十几道题。而且这些题里面，绝大多数都是 LeetCode 的热门面试题——103 题锯齿形层序遍历、107 题自底向上层序遍历、116 题填充每个节点的下一个右侧节点指针……全是这一个模板的变形。

更重要的是，层序遍历的思路在图的 BFS 里也完全适用。学好这一个知识点，等于打通了树和图 BFS 的任督二脉。

我见过不少人能写出递归的 DFS，但一问 BFS 就懵了，因为 BFS 没有那种"自然递归"的感觉，必须手动用队列来模拟。这篇文章就把这个手动模拟的过程讲清楚，然后展示如何用一个统一的模板解决 10 道变体题。

一、题目解析

题目：LeetCode 102. 二叉树的层序遍历

给你二叉树的根节点 root，返回其节点值的层序遍历结果（即逐层地，从左到右访问所有节点）。

示例：

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

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

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

考点梳理：

  1. BFS 的核心思想——用队列逐层处理
  2. 如何区分每一层的节点
  3. 层序遍历的各种变体

二、解法一：递归 DFS 模拟层序

思路

用 DFS 遍历，但带上层级信息 depth，把每个节点的值按层级写入对应的列表中。

完整代码

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }
    
    private void dfs(TreeNode node, int depth, List<List<Integer>> result) {
        if (node == null) return;
        
        // 如果这一层的列表还不存在，创建它
        if (depth == result.size()) {
            result.add(new ArrayList<>());
        }
        
        result.get(depth).add(node.val);
        dfs(node.left, depth + 1, result);
        dfs(node.right, depth + 1, result);
    }
}

复杂度分析

  • 时间复杂度：O(n)。每个节点访问一次。
  • 空间复杂度：O(n)。递归栈最深等于树的高度，最坏 O(n)。

三、解法二：BFS 标准队列实现

思路

用队列实现 BFS，关键在于如何"分层"——每次处理完当前队列里的所有节点（当前层），再处理它们的孩子（下一层）。

技巧：在每一层开始时，记录队列的当前大小 size，这就是当前层的节点数，处理 size 个节点后，队列里剩下的都是下一层的节点。

完整代码

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> level = new ArrayList<>();
            
            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);
            }
            
            result.add(level);
        }
        
        return result;
    }
}

复杂度分析

  • 时间复杂度：O(n)。每个节点进出队列一次。
  • 空间复杂度：O(n)。队列最大存储最宽一层的节点，完全二叉树的最后一层有 n/2 个节点，O(n)。

四、解法三：最优解法——双队列优化（避免 size 计算）

思路

用两个队列交替使用，一个存当前层，一个存下一层，避免每次都要记录 size。实际上性能相同，但代码结构更清晰。

另外给出所有常见变体的实现模板，展示一个模板能解决多少题。

完整代码（标准层序 + 所有变体）

// 标准层序遍历（102）
class Solution102 {
    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> level = new ArrayList<>();
            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);
            }
            result.add(level);
        }
        return result;
    }
}

// 变体1：锯齿形层序遍历（103）
// 奇数层从左到右，偶数层从右到左
class Solution103 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean leftToRight = true;  // 控制方向
        while (!queue.isEmpty()) {
            int size = queue.size();
            LinkedList<Integer> level = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (leftToRight) level.addLast(node.val);
                else level.addFirst(node.val);  // 反向插入
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
            leftToRight = !leftToRight;
        }
        return result;
    }
}

// 变体2：自底向上层序遍历（107）
// 返回从叶子节点到根节点的层次遍历
class Solution107 {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> result = new LinkedList<>();  // 注意用 LinkedList
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            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);
            }
            result.addFirst(level);  // 头插，最后一层排在最前面
        }
        return result;
    }
}

// 变体3：每层最大值（662的变体，返回每层最大值）
class SolutionMaxPerLevel {
    public List<Integer> largestValues(TreeNode root) {
        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();
            int maxVal = Integer.MIN_VALUE;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                maxVal = Math.max(maxVal, node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(maxVal);
        }
        return result;
    }
}

// 变体4：每层右视图（199）
// 返回从右侧看到的节点值（每层最右边的节点）
class Solution199 {
    public List<Integer> rightSideView(TreeNode root) {
        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();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == size - 1) result.add(node.val);  // 每层最后一个节点
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return result;
    }
}

// 变体5：每层平均值（637）
class Solution637 {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            double sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                sum += node.val;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(sum / size);
        }
        return result;
    }
}

Mermaid 图——BFS 队列变化过程

复杂度分析

所有变体相同：

  • 时间复杂度：O(n)。每个节点进出队列一次。
  • 空间复杂度：O(n)。队列存储最宽层的节点，O(n)。

提交结果：时间击败约 99% 用户，空间击败约 70% 用户（队列本身有额外开销）。

五、举一反三

10 道层序遍历变体题汇总

题号变体描述关键修改
102标准层序基础模板
103锯齿形交替方向插入
107自底向上结果头插
116填充右侧指针层内节点相连
117填充右侧指针II同116，不完全二叉树
199右视图取每层最后节点
515每层最大值层内取最大
637每层平均值层内求均值
429N叉树层序多个子节点入队
993堂兄弟节点记录深度和父节点

BFS 层序通用模板

Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
    int size = queue.size();  // 当前层节点数
    for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        // 【在这里处理当前节点】
        // i == 0：第一个节点
        // i == size-1：最后一个节点
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    // 【在这里处理当前层的统计结果】
}

六、踩坑实录

坑一：没有记录 size，导致无法区分层

// 错误写法：全程只有一个列表
while (!queue.isEmpty()) {
    TreeNode node = queue.poll();
    result.add(node.val);  // 所有节点放到同一个列表里
    ...
}

区分层的关键就是在处理每层之前记录 int size = queue.size()，然后用 for (int i = 0; i < size; i++) 处理恰好当前层的节点数，不多不少。

坑二：103 锯齿形用翻转替代头插，性能差

有人这样写：

if (!leftToRight) Collections.reverse(level);

翻转 List 是 O(n) 的，用 LinkedList 的 addFirst/addLast 控制方向是 O(1) 的。虽然总时间复杂度不变，但在常数因子上有差距。

坑三：107 自底向上用 addFirst 但用的是 ArrayList

ArrayList.add(0, element) 是 O(n) 的（需要移动元素），LinkedList.addFirst(element) 是 O(1) 的。自底向上层序遍历建议用 LinkedList<List<Integer>> 作为结果容器。

坑四：N叉树层序遍历忘记遍历所有子节点

// 二叉树：
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);

// N叉树：
for (Node child : node.children) {
    if (child != null) queue.offer(child);
}

从二叉树扩展到 N 叉树，只需要把两行压队列改成遍历 children 列表。

坑五：root 为 null 时不做判断直接进队列

queue.offer(null) 不会报错，但随后的 node.val 会 NPE。必须在开头加 if (root == null) return result;。

七、总结

层序遍历的 BFS 模板是二叉树题库里最高产的一个模板，掌握这一个模板，上面列出的 10 道变体题基本都能秒杀。

模板的核心是三点：队列存储待处理节点、每轮处理前记录 size 以区分层、处理完当前节点后把子节点入队。理解了这三点，不管题目怎么变形，改的只是"在哪里记录节点值"或者"以什么方式记录"。

BFS 的思维方式在图论里同样重要——最短路径、连通分量、拓扑排序，很多图算法的核心都是 BFS。树的 BFS 是更简单的热身，把模板练熟了，图的 BFS 就有了坚实的基础。

10 道变体题你都能一眼看出怎么改吗？评论区测试一下，觉得有用的话点个在看。

编辑此页
最近更新:
贡献者: xiaozhangge