代码随想录算法训练营第13天—二叉树02 | ● *层序遍历（对应10道题） ● *226.翻转二叉树 ● 101.对称二叉树
*层序遍历（二叉树的广度优先搜索，对应10道题）
102.二叉树的层序遍历(opens new window)
107.二叉树的层次遍历II(opens new window)
199.二叉树的右视图(opens new window)
637.二叉树的层平均值(opens new window)斜体样式
429.N叉树的层序遍历(opens new window)
515.在每个树行中找最大值(opens new window)
116.填充每个节点的下一个右侧节点指针(opens new window)
117.填充每个节点的下一个右侧节点指针II(opens new window)
104.二叉树的最大深度(opens new window)
111.二叉树的最小深度
- 考点
- 队列
- 我的思路
- 和视频讲解思路一致
- 视频讲解关键点总结
- 利用队列实现二叉树层序遍历（因为直接利用二叉树数据结构无法实现逐层遍历，同时层序遍历要求先查询的元素先处理，因此使用队列）
- 两层嵌套循环，初始将根节点加入队列
- 外层循环判断队列是否为空（每次外层循环遍历当前层节点，同时查询所有下一层节点）
- 在循环的开始记录队列的初始长度，代表当前层的节点数量
- 开始内层循环，循环次数即为当前层节点数量
- 循环开始，从队列中取顶层元素，将其加入最终的结果列表
- 判断该元素（节点）是否有左右子节点，若有，加入队列
- 进行下一次循环
- 返回最终结果
- 我的思路的问题
- 无
- 代码书写问题
- python里的queue.Queue对象不能直接作为循环的判断条件，其不支持布尔值测试，因为该类里没有进行布尔值转换的方法，因此当使用其作为判断条件时，由于该对象始终是一个对象，即条件为True，将发生无限循环（合理的方式是使用其empty方法来作为判断条件）
- 可执行代码
# 102.二叉树的层序遍历(opens new window)
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
my_queue = queue.Queue()
my_queue.put(root)
result = []
while not my_queue.empty():
size = my_queue.qsize()
level = []
while size:
size -= 1
cur = my_queue.get()
level.append(cur.val)
if cur.left:
my_queue.put(cur.left)
if cur.right:
my_queue.put(cur.right)
result.append(level)
return result
# 107.二叉树的层次遍历II(opens new window)
# 题目要求逆序层次遍历，此时相较于102题的代码，只需要额外在输出之前调用列表的reverse函数逆序返回或[::-1]进行逆序切片即可
*226.翻转二叉树
题目链接/文章讲解/视频讲解：https://programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html
- 考点
- 二叉树遍历+变量交换
- 我的思路
- 无
- 视频讲解关键点总结
- 在遍历的基础上进行变量交换
- 我的思路的问题
- 无
- 代码书写问题
- 无
- 可执行代码
# 二叉树深度优先前序遍历（递归）+变量交换
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return root
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
101.对称二叉树（先过年休息，年后再补上）
题目链接/文章讲解/视频讲解：https://programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html