一个组织结构页面需要先显示总负责人,再显示下一层负责人,最后显示各个小组成员。数据之间存在上下级关系,按照输入顺序逐个输出,未必能得到想要的层次。
这次要解决的问题是:给定一棵二叉树,把节点从上到下、同层从左到右分组返回。 解决它需要一种能记住“接下来该处理谁”的容器——队列。
本篇是算法入门系列第六篇,使用 Java 17 及以上版本。系列目录收录了完整学习顺序;上一篇的递归与归并排序介绍了函数调用如何逐层展开。
一、先弄清楚:谁先进去,谁先出来
假设依次放入任务 A、B、C。如果最先取出 A,然后是 B、C,这是队列,遵守先进先出,通常缩写为 FIFO。
如果最先取出 C,然后是 B、A,这是栈,遵守后进先出,通常缩写为 LIFO。可以把栈想成叠起来的盘子,最后放上去的盘子最先取走。
| 容器 | 放入顺序 | 取出顺序 | 适合表达的事情 |
|---|---|---|---|
| 栈 | A、B、C | C、B、A | 最近的一步先处理,例如嵌套括号 |
| 队列 | A、B、C | A、B、C | 按发现顺序处理,例如逐层扩展 |
容器的选择决定了处理顺序。在上一节的递归里,尚未完成的函数调用就由调用栈保存:内层调用先返回,外层调用才能继续。
在 Java 中,ArrayDeque 可以用作栈,也可以用作队列。作为栈时,可以从同一端 push、pop;作为队列时,使用 offer 加入队尾、poll 取出队首。本篇通过 Queue<Node> 类型表达队列意图。
这些方法需要保持一套一致的使用方式。把入队和入栈操作混用,虽然代码可能编译通过,处理顺序却会改变。
二、用一棵小树确定输入和输出
树由节点和连接节点的关系组成。最上面的节点叫根节点,一个节点向下直接连接的节点叫子节点。二叉树中,每个节点最多有左、右两个子节点。
这里使用下面这棵树:
1 / \ 2 3 / \ \ 4 5 6预期返回:
[[1], [2, 3], [4, 5, 6]]外层列表表示所有层,里面的每个列表表示一层。空树没有任何层,应返回 []。
节点定义如下,放在完整示例的 TreeBfs 类中:
public static class Node { final int value; Node left; Node right;
public Node(int value) { this.value = value; }}一个 Node 保存当前数值,以及左右子节点的引用。没有某个子节点时,对应引用为 null。树里的数字可以重复,遍历顺序取决于连接关系,与数值大小无关。
本文约定输入确实是一棵树:没有环,也没有两个父节点共享同一个子节点。普通组织结构可能有任意多个直接下级,需要把左右引用改成子节点列表;逐层处理的思路仍然适用。
三、队列为什么能让节点一层一层出现
先把根节点放进队列。每次取出队首节点,把它的左、右子节点依次加入队尾。
| 当前动作 | 动作后的队列,左边是队首 | 已取出的节点 |
|---|---|---|
| 放入根节点 | [1] | [] |
| 取出 1,放入 2、3 | [2, 3] | [1] |
| 取出 2,放入 4、5 | [3, 4, 5] | [1, 2] |
| 取出 3,放入 6 | [4, 5, 6] | [1, 2, 3] |
| 依次取出 4、5、6 | [] | [1, 2, 3, 4, 5, 6] |
处理节点 2 时,虽然已经发现了节点 4、5,它们仍然排在节点 3 后面。因此,上一层的节点会先处理完,下一层才轮到。
这种从起点向外逐层扩展的方式叫作广度优先搜索,缩写为 BFS。这里“搜索”不一定表示寻找某一个目标,也可以表示访问所有可达节点。
如果改用栈,刚放进去的子节点很快就会被取出,处理过程可能沿着一个分支先往下走。这更接近深度优先遍历的顺序,不能直接得到当前要求的逐层分组。
四、关键一步:先记住这一层有多少节点
队列保证了先后顺序,但返回结果还要区分层。处理一层之前,队列中恰好装着这一层的节点;记录此时的长度,再取出相同数量的节点即可。
下面是完整示例中的核心方法,省略了类定义和导入:
public static List<List<Integer>> levels(Node root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<Node> queue = new ArrayDeque<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < size; i++) { Node node = queue.poll(); level.add(node.value); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(level); } return result;}第一轮记录 size = 1,只取出根节点。虽然处理过程中加入了两个子节点,本轮仍然只处理一个节点。
第二轮记录 size = 2,只取出 2、3。它们的子节点加入队尾,留到第三轮处理。每轮结束时,把当前层的列表加入结果,层与层就分开了。
不要把循环条件写成 i < queue.size()。队列会随着出队和入队不断变化,它的实时长度已经不再表示本轮需要处理多少项,可能造成漏处理或者混入下一层。
还有两个边界在代码中单独处理:空根节点直接返回;不存在的子节点不入队。ArrayDeque 不接受 null,因此不能用“把空节点也塞进去,以后再判断”的写法。
五、运行后看什么结果
下载完整 TreeBfs.java,或者下载系列源码包。在文件所在目录运行:
javac -encoding UTF-8 TreeBfs.javajava TreeBfs预期输出:
[[1], [2, 3], [4, 5, 6]][]第一行对应前面画出的树,第二行对应空树。再把示例改成只有一个根节点,应得到 [[1]];改成只有右子节点的长链,则每层只有一个数。
测试树结构时,至少包含空树、单节点、只有一个方向的链、同层有多个节点的树。只测试完整的三层树,很容易漏掉空引用处理问题。
六、时间和空间分别花在哪里
设节点总数为 n,最大一层的节点数为 w。每个节点入队一次、出队一次,并把自己的数值加入结果一次,总时间复杂度是 O(n)。
代码中虽然有 while 和 for 两层循环,但它们共同处理的是全部 n 个节点。内层循环的次数随着每层宽度变化,所有层的次数加起来仍然是 n,不能直接按代码层数判断成 O(n²)。
队列可能同时保存当前层剩余节点和下一层已发现节点,其规模是 O(w)。当前层列表也是 O(w)。返回结果最终保存全部节点数值,另需 O(n) 空间。
因此,排除返回结果,辅助空间为 O(w);把结果也算进去,总额外空间为 O(n)。一条链的队列很小,一棵很宽的树却可能让队列占用大量空间。
七、从树走向图时,要增加什么
树中每个非根节点只有一个父节点,沿子节点访问时不会走回已经处理的地方。图可能存在环,也可能通过不同路径到达同一个节点。
在图上使用 BFS 时,通常要维护已访问集合,并在节点入队时标记。否则,同一个节点可能多次入队;遇到环时,甚至会不断重复访问。
BFS 还能用于无权图,或所有边权相同的图,寻找边数最少的路径。这依赖于“多走一条边,代价增加相同”这一前提。边权不同时,先到达某个节点的路径未必代价最小,需要选择适合权重条件的算法。
本篇的 levels 只处理约定好的树,没有包含图的去重和最短路功能。
八、练习:返回每一层的最大值
继续使用示例树,把返回结果改为:
[1, 3, 6]处理一层之前建立当前层的最大值,遍历这一层时更新,结束后把一个数加入结果。层边界的处理可以直接沿用。
再用全为负数的树验证,例如根节点为 -5,两个子节点是 -8、-3,应返回 [-5, -3]。最大值不能默认从 0 开始,应使用本层第一个节点,或 Integer.MIN_VALUE。
空树仍返回 []。先手工推演这三种输入,再改动代码,能帮助你分清“怎样分层”和“每一层计算什么”这两个职责。
下一篇学习回溯与全部子集,我们会沿着选择逐步深入,再返回上一层尝试其他选择。
If this article helped you, please share it with others!
Some information may be outdated






