往期博客：

Leetcode1-两数之和详解

Leetcode2-两数相加代码详解

Leetcode20-有效的括号详解

Leetcode21-合并两个有序链表详解

Leetcode22-有效括号生成详解

Leetcode24-两两交换链表中的节点详解

Leetcode27-移除元素详解

Leetcode46-全排列详解

Leetcode49-字母异位分组详解

Leetcode53-最大子数组和详解

Leetcode56-合并区间详解

LeetCode57-插入区间详解

Leetcode77-组合详解

Leetcode78-子集详解

Leetcode90-子集II详解

Leetcode94-二叉树的中序遍历详解

目录

题目

示例

解析

广度优先搜索

深度优先搜索

代码

广度优先搜索

深度优先搜索

题目

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

题目分析

已知：二叉树根节点

目的：层序遍历

要求：从左到右访问二叉树

---

示例

示例1

输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]

示例2

输入：root = [1] 输出：[[1]]

示例3

输入：root = [] 输出：[]

---

解析

广度优先搜索

对于示例1，二叉树总共有3层，层序遍历需要先遍历第一层得到子集[3]，再遍历第二层得到子集[9,20]，最后遍历最后一层得到子集[15,7]。对于Leetcode94-二叉树的中序遍历这一题中遍历的大致方向是从上到下遍历，但是输出是从下到上输出，因为要从上到下找到最左左节点，然后从上到下从最左左节点一次输出，这满足栈的先进后出的特点，所以用栈方法来做题。而本题是逐层遍历，即从上到下遍历，并从上到下输出，这就满足了队列先进先出的思想，所以本题可以使用队列来做题。

 首先初始化三个变量，其中res存放每一层遍历的子集，size为每一层节点个数，queue为队列

 遍历第一层时，size=1，将节点3加入队列中，此时size=1，则只从队列中取出一个元素，即元素3，放到结果集中

此时，将节点3的左右孩子加入队列中，size=2 ，在出队的时候，先出9，当出9后查看节点9有没有左右孩子，有的话紧接着入队，没有的话出20，因为size=2，所以只出2个元素。

最后入队15和7，再逐一出队

 深度优先搜索

深度优先搜索是从上到下遍历二叉树的，所以这跟题目要求逐层遍历是相斥的，但是既然深度优先搜索是从上到下遍历那么可以根据层将元素归类，此时要确定每个元素属于那一层，并将该元素放入对应层的子集中。

例如对于如下二叉树，总共包含3层 ，那么他的结果集中一定包含3个子集，每个子集包含每层的元素

首先遍历第一层即root节点1，节点1属于0层节点，所以将3放入子集0中，然后遍历到节点2，及节点2属于1层，则将2放入子集1中，然后遍历到节点4，节点4属于2层，则将4放入子集2，依次进行直到所有节点遍历完 

代码

广度优先搜索

class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: result = [] if root is None: return result q = deque([]) # 创建队列 q.append(root) # 将根节点加入队列中 while len(q) > 0: size = len(q) ls = [] # 用于存放每一层遍历到的节点 while size > 0: cur = q.popleft() ls.append(cur.val) if cur.left is not None: q.append(cur.left) if cur.right is not None: q.append(cur.right) size = size-1 result.append(ls[:]) return result

深度优先搜索

class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: result = [] if root is None: return result self.dfs(root, result, 0) return result def dfs(self, node, result, level): if node is None: return if level > len(result)-1: result.append([]) # 向结果集中谈价空子集，用来存放当前层的元素 result[level].append(node.val) if node.left is not None: self.dfs(node.left, result, level+1) if node.right is not None: self.dfs(node.right, result, level+1)