题⽬描述

从上到下按层打印⼆叉树，同⼀层结点从左⾄右输出。每⼀层输出⼀⾏。

给定的⼆叉树是 {1,2,3,#,#,4,5} : 该⼆叉树多⾏打印层序遍历的结果是：

示例1 输⼊：{8,6,10,5,7,9,11} 返回值：[[8],[6,10],[5,7,9,11]]

思路及解答

59题的缩减版

迭代法BFS（广度优先搜索）

  • 时间复杂度：O(n)，每个节点恰好入队和出队各一次

  • 空间复杂度：O(n)，队列中最多存储n个节

递归DFS（深度优先搜索）

虽然层序遍历通常用BFS，但也可以用DFS通过递归隐式维护层级信息来实现

  • 时间复杂度：O(n)，每个节点访问一次

  • 空间复杂度：O(h)，递归栈深度等于树高，最坏情况O(n)