[Leetcode 102] 二叉树的层序遍历

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

解法一:BFS(推荐)

BFS 的特点就是“从上到下,从左到右,一圈一圈往外扩”,而层序遍历正好就是在利用BFS的特性。
  1. 先把根节点放入队列;
  1. 然后每次从队列中取出当前层的所有节点;
  1. 对于每个取出的节点,把它的左右孩子(如果存在)加入队列;
  1. 当前层处理完后,再处理下一层。
为了“分层输出”,我们可以在每一轮循环里记录这一层有多少个节点,然后只循环这一层的数量。
循环结束后,这一层的结果(一个列表)就完整收集起来了。
队列的先进先出性质,天然保证了节点是按层、按从左到右的顺序被访问的。
复杂度:
  • 时间:O(N),每个节点都被访问一次。
  • 空间:O(N),最坏情况下(完全二叉树)队列里可能同时有 N/2 个节点。

解法二:DFS

DFS 也可以实现层序遍历,关键在于递归时携带“当前层数 level”这个参数
当我们到达某一层节点时,如果结果列表还没有那一层的列表,就新建一个,然后把当前节点值加进去。
这就像是我们自己在模拟“第几层”的概念,虽然递归是深度优先的,但我们依然能按层分类收集节点。
这样,每个节点都能知道自己在第几层(通过递归参数),只要把它的值放到 res[level] 里,就能把同层的节点聚在一起。
递归顺序(先左后右)保证了每层节点在结果中从左到右的顺序。
复杂度
  • 时间:O(N),每个节点访问一次;
  • 空间:O(h),递归栈的深度(h 为树高),最坏情况 O(N)。
Buy Me a Coffee
上一篇
[Leetcode 101] 对称二叉树
下一篇
[Leetcode 105] 从前序与中序遍历序列构造二叉树