剑指 Offer 32 - II. 从上到下打印二叉树 II-轻识

剑指 Offer 32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:
给定二叉树: [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
返回其层次遍历结果：

[
[3],
[9,20],
[15,7]
]

提示：

节点总数 <= 1000

题目解析

I. 按层打印：题目要求的二叉树的从上至下打印（即按层打印），又称为二叉树的广度优先搜索（BFS）。BFS 通常借助队列的先入先出特性来实现。

II. 每层打印到一行：将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。

题目解答

代码展示

方法一：广度优先搜索层次遍历法（递归）

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = None
class Solution:       def levelOrder(self, root: TreeNode) -> List[List[int]]:        '''            方法一：广度优先搜索 层次遍历法（递归）        '''        # step 1：判空        res = []        if not root:            return res        # step 2：广度优先搜索        level = 0        res=self.bfs(root,0,res)        return res
    # 方法：广度优先搜索    def bfs(self,root,level,res):        # step 1：终止条件判断        if level==len(res):            res.append([])        # step 2：先根->左->右        res[level].append(root.val)        if root.left:            self.bfs(root.left,level+1,res)        if root.right:            self.bfs(root.right,level+1,res)        return res

方法二：队列迭代 (非递归)

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = None
class Solution:    def levelOrder(self, root: TreeNode) -> List[List[int]]:        '''            方法二：队列迭代 (非递归)        '''        res = []        if not root:            return res         queue = collections.deque()        queue.append(root)        while queue:            level = []            for _ in range(len(queue)):                node = queue.popleft()                level.append(node.val)                if node.left:                    queue.append(node.left)                if node.right:                    queue.append(node.right)            res.append(level)        return res

复杂度计算

时间复杂度：O(N)，其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为 O(N)。
-空间复杂度：O(N)，当树为平衡二叉树时，最多有N/2个树节点入队，使用 O(N) 大小的额外空间

运行结果

方法一：广度优先搜索层次遍历法（递归）

方法二：队列迭代 (非递归)