给定二叉树的根节点
root,返回节点值的层序遍历(即逐层地,从左到右访问所有节点)。示例 1:

示例 2:
示例 3:
解法一:BFS(推荐)
BFS 的特点就是“从上到下,从左到右,一圈一圈往外扩”,而层序遍历正好就是在利用BFS的特性。
- 先把根节点放入队列;
- 然后每次从队列中取出当前层的所有节点;
- 对于每个取出的节点,把它的左右孩子(如果存在)加入队列;
- 当前层处理完后,再处理下一层。
为了“分层输出”,我们可以在每一轮循环里记录这一层有多少个节点,然后只循环这一层的数量。
循环结束后,这一层的结果(一个列表)就完整收集起来了。
队列的先进先出性质,天然保证了节点是按层、按从左到右的顺序被访问的。
复杂度:
- 时间:O(N),每个节点都被访问一次。
- 空间:O(N),最坏情况下(完全二叉树)队列里可能同时有 N/2 个节点。
解法二:DFS
DFS 也可以实现层序遍历,关键在于递归时携带“当前层数 level”这个参数。
当我们到达某一层节点时,如果结果列表还没有那一层的列表,就新建一个,然后把当前节点值加进去。
这就像是我们自己在模拟“第几层”的概念,虽然递归是深度优先的,但我们依然能按层分类收集节点。
这样,每个节点都能知道自己在第几层(通过递归参数),只要把它的值放到
res[level] 里,就能把同层的节点聚在一起。递归顺序(先左后右)保证了每层节点在结果中从左到右的顺序。
复杂度
- 时间:O(N),每个节点访问一次;
- 空间:O(h),递归栈的深度(h 为树高),最坏情况 O(N)。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-102-二叉树的层序遍历
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
上一篇
[Leetcode 101] 对称二叉树
下一篇
[Leetcode 105] 从前序与中序遍历序列构造二叉树
