算法|算法:从上到下打印二叉树

算法|算法:从上到下打印二叉树

文章图片

算法|算法:从上到下打印二叉树

文章图片


【算法|算法:从上到下打印二叉树】
从上到下打印出二叉树的每个节点 , 同一层的节点按照从左到右的顺序打印 。
示例给定二叉树: [3920nullnull157

3
/ \\
9 20
/ \\
15 7
返回:
[3920157

提示

  • 节点总数 <= 1000
方法:迭代BFS迭代第一层:根节点 出队列 , 存入到结果集合中 , 发现左/右子节点存在 , 存入到队列中;

迭代第二层:左子节点 出队列 , 存入到结果集合中 , 发现左/右子节点不存在 , 跳出本次循环;右子节点 出队列 , 存入到结果集合中 , 发现左/右子节点存在 , 存入到队列中 。

终止条件:循环上述步骤 , 直至迭代完所有节点 , 跳出循环;遍历结果集合 , 转化为数组返回 , 即可 。
代码如下:

复杂度分析
  • 时间复杂度: O(N) , N 为二叉树的节点数量 , 即 BFS 需循环 N 次 。
  • 空间复杂度: O(N) , 最差情况下 , 即当树为平衡二叉树时 , 最多有 N/2 个树节点同时在 queue 中 , 使用 O(N) 大小的额外空间 。
END本文内容出处是力扣官网 , 希望和大家一起刷算法 , 在后面的路上不变秃但是变强!
好兄弟可以点赞并关注我 , 全部都是干货 。