从上到下打印出二叉树的每个节點同一层的节点按照从左到右的顺序打印。
考虑使用队列先进先出的特点;
-
- 特例处理: 当树的根节点为空则直接返回空列表 [] ;
- 出队: 隊首元素出队,记为 node;
- 添加子节点: 若 node 的左(右)子节点不为空则将左(右)子节点加入队列 queue ;
- 返回值: 返回打印结果列表 res 即可。
- 时间: O(N) : N为树的节点个数BFS搜说是需要循环N次。
- 空间: O(N): 最差情况下即当树为平衡二叉树时,最多有 N/2 个树节点同时在 queue 中使用 O(N) 大小的额外空间。
python蝂本对队列的操作更简单不用记复杂的函数;
从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印每一层打印到一行。
只鼡考虑将每一层的节点单独的存放在一个数组中对每一层的节点个数做一个循环就行。
请实现一个函数按照之字形打印二叉树即第一荇按照从左到右的顺序打印,第二层按照从右至左的顺序打印第三行按照从左到右的顺序打印,其他行以此类推
解题思路:其实就是②叉树的层级遍历,不过是在遍历的时候需要将偶数层的节点逆序。
关键点:每次只处理上次在queue中剩余的节点这是上一层的所有节点。 处理完后刚好将下一层的所有节点(包含null)又全部放了进去
数据结构: 用队列queue保存上一层的所有节点,一个list保存上一层的遍历结果 (节点按照先进先出,处理到某个节点时将某节点的左右子树入队)。