YCBlogs 算法笔记：从上往下打印二叉树——队列实现层序遍历（BFS）原理与实战-北京尧图网络

教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载导读从上往下打印二叉树是二叉树遍历类问题中的经典面试题常见于《剑指 Offer》第 32 题其本质是二叉树的广度优先遍历BFS即层序遍历Level Order Traversal。本文以 YCBlogs 仓库 leetcode/05.树/14.从上往下打印二叉树.md 中的解题笔记为主体结合仓库内二叉树与队列的系列源码完整讲解题目要求、队列算法原理、Java 实现细节、复杂度分析以及按层一行打印之字形打印等进阶变体帮助你彻底掌握这类借助辅助数据结构完成遍历的题型。01. 题目要求从上往下打印出二叉树的每个结点同一层的结点按照从左向右的顺序打印。示例给定如下二叉树8 / \ 6 10 / \ / \ 5 7 9 11则应依次打印出8、6、10、5、7、9、11。从输出结果可以直观看到先打印根结点 8再打印第二层 6、10从左到右最后打印第三层 5、7、9、11从左到右。这与前序、中序、后序遍历完全不同——它严格按树的层次从上到下、同一层内从左到右的顺序访问每个结点。02. 问题分析这道题考查的遍历本质原笔记明确指出这道题实质是考查树的遍历算法。从上到下打印二叉树的规律是每一次打印一个结点的时候如果该结点有子结点则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点重复前面的打印操作直至队列中所有的结点都被打印出来为止。2.1 为什么必须用队列队列是一种**先进先出FIFO**的操作受限线性表入队enqueue把数据放到队尾出队dequeue从队头取元素。仓库笔记 leetcode/04.队列/01.队列基础介绍.md 中对队列做了形象比喻就像排队买票先来的先买后来的人只能站末尾不允许插队。层序遍历之所以选择队列正是因为先被访问的结点的子结点必须比后被访问的结点的子结点更早被访问根结点 8 先入队、先出队打印打印 8 时它的两个孩子 6、10 依次入队排在队尾队头此时是 6所以先打印 6再把 6 的孩子 5、7 排到 10 的后面接着打印 10把 10 的孩子 9、11 排到队尾之后依次打印 5、7、9、11。整个过程保证上一层所有结点打印完之前下一层结点只会排在队尾等待从而天然实现了从上到下、从左到右的输出顺序。2.2 与深度优先遍历DFS的对比仓库笔记 leetcode/05.树/02.实现二叉树.md 中总结了二叉树经典的前序、中序、后序遍历并指出树的深度优先遍历需要用到额外的数据结构——栈而广度优先遍历需要队列来辅助。遍历方式访问顺序辅助数据结构实现方式前序遍历根 → 左子树 → 右子树栈或递归调用栈深度优先 DFS中序遍历左子树 → 根 → 右子树栈或递归调用栈深度优先 DFS后序遍历左子树 → 右子树 → 根栈或递归调用栈深度优先 DFS层序遍历逐层、每层从左到右队列广度优先 BFS从数据结构选型上理解DFS 要一路走到黑再回头用栈保存回溯点BFS 要层层推进用队列保持待访问结点的先后次序。本题正是 BFS 在二叉树上的直接应用。03. 实例代码详解原笔记给出了完整的 Java 实现先看结点定义与核心算法public class Test { /** * 二叉树的树结点 */ public static class BinaryTreeNode { int value; BinaryTreeNode left; BinaryTreeNode right; } /** * 从上往下打印出二叉树的每个结点同一层的结点按照从左往右的顺序打印。 * 例如如下二叉树 * 8 * / \ * 6 10 * / \ / \ * 5 7 9 11 * 则依次打印出 8、6、10、5、7、9、11。 * * param root 树的结点 */ public static void printFromToBottom(BinaryTreeNode root) { // 当结点非空时才进行操作 if (root ! null) { // 用于存放还未遍历的元素 QueueBinaryTreeNode list new LinkedList(); // 将根结点入队 list.add(root); // 用于记录当前处理的结点 BinaryTreeNode curNode; // 队列非空则进行处理 while (!list.isEmpty()) { // 删除队首元素 curNode list.remove(); // 输出队首元素的值 System.out.print(curNode.value ); // 如果左子结点不为空则左子结点入队 if (curNode.left ! null) { list.add(curNode.left); } // 如果右子结点不为空则右子结点入队 if (curNode.right ! null) { list.add(curNode.right); } } } } }3.1 逐步拆解算法流程判空保护root null时直接跳过空树不输出任何内容初始化队列QueueBinaryTreeNode list new LinkedList()注意 Java 中队列通常使用LinkedList作为Queue接口的实现类根结点入队list.add(root)这是遍历的起点循环出队while (!list.isEmpty())表示只要还有待打印结点就继续取出队首curNode list.remove()remove()删除并返回队首元素打印当前结点System.out.print(curNode.value )左、右子结点依次入队先左后右这是同一层从左到右顺序的关键——因为队列是 FIFO先入队的左孩子必然先被取出打印。3.2 Java Queue 常用 API 对照原代码使用了add/remove/isEmpty三个方法。在面试中也可以使用带返回值的方法它们的行为差异如下方法作用失败时行为add(e)/offer(e)入队追加到队尾add抛异常offer返回falseremove()/poll()出队删除并返回队首remove抛异常poll返回nullelement()/peek()查看队首但不删除element抛异常peek返回null3.3 可复制运行的完整版本原笔记代码为便于讲解省略了构造器与测试入口下面补充成可直接运行的完整类便于本地验证输出结果import java.util.LinkedList; import java.util.Queue; public class BinaryTreeLevelOrder { // 树结点定义 public static class BinaryTreeNode { int value; BinaryTreeNode left; BinaryTreeNode right; public BinaryTreeNode(int value) { this.value value; } } // 层序遍历从上往下、同一层从左到右打印 public static void printFromToBottom(BinaryTreeNode root) { if (root null) { return; } QueueBinaryTreeNode queue new LinkedList(); queue.add(root); // 根结点入队 while (!queue.isEmpty()) { BinaryTreeNode cur queue.remove(); // 取出队首 System.out.print(cur.value ); if (cur.left ! null) { queue.add(cur.left); // 左孩子入队 } if (cur.right ! null) { queue.add(cur.right); // 右孩子入队 } } System.out.println(); } public static void main(String[] args) { // 构造示例二叉树 // 8 // / \ // 6 10 // / \ / \ // 5 7 9 11 BinaryTreeNode n8 new BinaryTreeNode(8); BinaryTreeNode n6 new BinaryTreeNode(6); BinaryTreeNode n10 new BinaryTreeNode(10); BinaryTreeNode n5 new BinaryTreeNode(5); BinaryTreeNode n7 new BinaryTreeNode(7); BinaryTreeNode n9 new BinaryTreeNode(9); BinaryTreeNode n11 new BinaryTreeNode(11); n8.left n6; n8.right n10; n6.left n5; n6.right n7; n10.left n9; n10.right n11; printFromToBottom(n8); // 期望输出8 6 10 5 7 9 11 printFromToBottom(null); // 期望输出空无任何输出 } }04. 边界情况与注意事项空树root null时不应抛异常直接返回即可单结点树只有一个根结点时入队一次、出队打印一次队列即空输出正确只有左子树或右子树的树curNode.left或curNode.right为null时跳过入队不会把null放进队列避免空指针先入队左孩子还是右孩子本题要求同一层从左到右因此必须先左后右。若题目改成从右到左则交换两条入队语句的顺序即可输出格式原代码用System.out.print(curNode.value )结点之间以空格分隔面试中如需返回List只需把打印语句替换为list.add(curNode.value)。05. 复杂度分析时间复杂度O(n)其中 n 为二叉树结点总数。每个结点恰好入队一次、出队一次循环体内的操作出队、打印、子结点入队均为常数时间总执行次数与结点数成正比。空间复杂度O(n)。最坏情况下如一棵完全二叉树的最底层队列中需要同时容纳接近 n/2 个结点一般记为 O(n)更精确地说是 O(w)w 为二叉树的最大宽度。参考仓库笔记 leetcode/00.导向/02.算法基础导论.md 中的大 O 表示法思想复杂度分析关注的是执行时间随数据规模增长的变化趋势这里队列中每个结点的处理次数是常数级的因此整体呈线性增长趋势记作 O(n)。06. 扩展从仓库源码看层序遍历的进阶变体从上往下打印二叉树是一系列层序类题目的基础形态。YCBlogs 仓库在 leetcode/05.树目录下收录了多个直接相关的进阶变体理解这些变体可以帮你建立完整的层序遍历解题框架。6.1 变体一按层打印每层一行题目 leetcode/05.树/19.二叉树打印出多行.md 要求在基本层序遍历的基础上把每一行单独打印到一行里。解法是在队列基础上增加两个计数器// 当前层的结点个数 int current 1; // 记录下一层的结点个数 int next 0;核心逻辑每从队列取出一个结点就current--每入队一个子结点就next。当current减到 0 时说明当前层已全部打印完此时System.out.println()换行并把current next; next 0重置开始处理下一层。这就是基础 BFS 层计数的经典模板也是后续解决锯齿形之字形遍历二叉树最大宽度等问题的基础。6.2 变体二之字形ZigZag顺序打印题目 leetcode/05.树/20.按之字形顺序打印二叉树.md 要求第一行从左到右、第二行从右到左、第三行再从左到右……交替打印。原笔记给出的解法是使用两个栈或两个列表如果当前打印的是奇数层则先保存左子结点再保存右子结点到一个栈里如果当前打印的是偶数层则先保存右子结点再保存左子结点到第二个栈里。核心思路由于栈是 LIFO当一行从左到右访问时把下一层结点先左后右压入栈弹出时自然变成从右到左反之先右后左压栈弹出时变成从左到右从而用入栈顺序的切换实现方向的交替。6.3 仓库中的通用层序遍历实现仓库笔记 leetcode/05.树/02.实现二叉树.md 第 08 节给出了一个基于ArrayDeque的通用层序遍历实现levelOrderTraversal算法骨架与本题完全一致可互为印证public void levelOrderTraversal() { if (root null) { System.out.println(empty tree); return; } ArrayDequeTreeNode queue new ArrayDequeTreeNode(); queue.add(root); while (queue.isEmpty() false) { TreeNode node queue.remove(); System.out.print(node.value ); if (node.left ! null) { queue.add(node.left); } if (node.right ! null) { queue.add(node.right); } } System.out.print(\n); }该实现用ArrayDequeTreeNode作为队列载体ArrayDeque同样实现了Queue接口add入队、remove出队逻辑与本题printFromToBottom完全一致可见队列先左后右入队是层序遍历的通用范式。07. 面试要点总结识别题型看到从上到下按层从左到右等关键词应立刻联想到层序遍历BFS辅助结构BFS 用队列FIFODFS 用栈——这是选型依据要能说清楚原因入队顺序同层从左到右打印必须先左孩子、后右孩子入队判空处理根结点判空、子结点判空缺一不可复杂度时间 O(n)、空间 O(n)并能解释最坏情况下队列宽度举一反三掌握基础层序遍历后能继续推导出每层一行加计数器与之字形打印双栈或双端队列等变体它们对应仓库中的 19.二叉树打印出多行.md 与 20.按之字形顺序打印二叉树.md 两篇笔记。通过本篇文章你不仅掌握了从上往下打印二叉树这一道题的标准解法更建立了以队列为核心的层序遍历方法论可以平滑迁移到所有 BFS 类二叉树问题中。赞分享教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载相关推荐CS-Notes 算法详解二叉树的层序遍历——从上往下打印二叉树剑指 Offer 32.1CS Notes 算法详解二叉树的层序遍历——从上往下打印二叉树剑指 Offer 32.1 本篇基于 CS Notes 仓库中《剑指 Offer》题解的第知识库文档教程猫抓 cat-catch 视频嗅探扩展上手指南4 条安装渠道、3 条路径一次讲清猫抓 cat catch 视频嗅探扩展上手指南4 条安装渠道、3 条路径一次讲清网页上的视频想存下来右键却只有复制视频地址直播流一闪而过根本抓不住音视频Hello Algo Python 实战基于队列的二叉树层序遍历BFS完整实现Hello Algo Python 实战基于队列的二叉树层序遍历BFS完整实现本文以《Hello 算法》仓库中的 Python 层序遍历实现为主线完整教程文档示例工程教育创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

YCBlogs 算法笔记：从上往下打印二叉树——队列实现层序遍历（BFS）原理与实战

相关推荐

性能测试指标体系详解：从RT、TPS到系统资源与稳定性

PO模式+数据驱动：打造低维护成本的UI自动化测试框架

用LangChain和Playwright构建大模型驱动的测试智能体

更多资讯

Flink/PyFlink CSV读写实战：Schema声明与参数配置避坑

LingBot-World 2.0能商用吗？CC BY-NC-SA 4.0许可证解读：14B权重的使用边界与风险清单

响应式实时数据处理：从概念到落地的完整技术链路

基于YOLOv8的路面裂缝检测系统：中英文双版实战

Portabase数据库恢复教程：如何从备份快照快速找回丢失的数据

cosmos-sdk 系统测试入门：从查询、JSON 断言到 Genesis 与交易驱动的状态测试

今日更新

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？