企业官网建设流程全解析

• 教程
• 技术博客
• 文档

导读

"从上往下打印二叉树"是二叉树遍历类问题中的经典面试题（常见于《剑指 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 要"一路走到黑再回头"，用栈保存回溯点；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) { // 用于存放还未遍历的元素 Queue<BinaryTreeNode> 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 逐步拆解算法流程

1. 判空保护：root == null时直接跳过，空树不输出任何内容；
2. 初始化队列：Queue<BinaryTreeNode> list = new LinkedList<>()，注意 Java 中队列通常使用LinkedList作为Queue接口的实现类；
3. 根结点入队：list.add(root)，这是遍历的起点；
4. 循环出队：while (!list.isEmpty())表示只要还有待打印结点就继续；
5. 取出队首：curNode = list.remove()，remove()删除并返回队首元素；
6. 打印当前结点：System.out.print(curNode.value + " ")；
7. 左、右子结点依次入队：先左后右，这是"同一层从左到右"顺序的关键——因为队列是 FIFO，先入队的左孩子必然先被取出打印。

3.2 Java Queue 常用 API 对照

原代码使用了add/remove/isEmpty三个方法。在面试中，也可以使用带返回值的方法，它们的行为差异如下：

3.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; } Queue<BinaryTreeNode> 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; } ArrayDeque<TreeNode> queue = new ArrayDeque<TreeNode>(); 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"); }

该实现用ArrayDeque<TreeNode>作为队列载体（ArrayDeque同样实现了Queue接口，add入队、remove出队），逻辑与本题printFromToBottom完全一致，可见"队列 + 先左后右入队"是层序遍历的通用范式。

07. 面试要点总结

1. 识别题型：看到"从上到下""按层""从左到右"等关键词，应立刻联想到层序遍历（BFS）；
2. 辅助结构：BFS 用队列（FIFO），DFS 用栈——这是选型依据，要能说清楚原因；
3. 入队顺序：同层从左到右打印，必须"先左孩子、后右孩子"入队；
4. 判空处理：根结点判空、子结点判空缺一不可；
5. 复杂度：时间 O(n)、空间 O(n)，并能解释最坏情况下队列宽度；
6. 举一反三：掌握基础层序遍历后，能继续推导出"每层一行"（加计数器）与"之字形打印"（双栈或双端队列）等变体，它们对应仓库中的 19.二叉树打印出多行.md 与 20.按之字形顺序打印二叉树.md 两篇笔记。

通过本篇文章，你不仅掌握了"从上往下打印二叉树"这一道题的标准解法，更建立了以队列为核心的层序遍历方法论，可以平滑迁移到所有 BFS 类二叉树问题中。

• 教程
• 技术博客
• 文档