同学们好，我是一名计算数学专业在读的研究生，正在准备转码，接下来的日子会在这个公众号上写一些我的学习心得，希望能帮助到大家。今天我们介绍的是二叉树层序遍历。在算法上，叫做广度优先搜索（BFS），它的核心只有一个，就是队列（Queue）
队列是一种 先进先出 (First In, First Out, FIFO) 的线性数据结构，就像生活中排队买奶茶：先排队的人先拿到奶茶离开。
在 Python 中，我们通常使用collections.deque（双端队列），因为它在处理弹出队头元素时效率极高。这里主要用到下面两个操作：
入队 (append)：新来的元素排在队尾（末端） 。
出队 (popleft)：最先进入队列的元素从队头（前端）弹出 。
2.下面给出层序遍历的“模板”
后面介绍的层序题目都是基于它“微调”出来的
from collections import deque''''''step1：初始化阶段判空处理：如果树根root是空的，直接返回空列表。容器准备：创建一个队列，并把根节点放进去作为种子。这时，队列里只有“第一层”的节点。''''''def levelOrder(root): if not root: return [] queue = deque([root]) # 核心容器：队列 result = []''''''step2：按层外循环 (while queue)只要队列里还有节点，就说明还没遍历完 。level_size：这是最精妙的一步.在处理某一层之前，先数一下队列里现在有多少个节点。这确保了接下来的 for 循环只处理属于“当前这一层”的节点，而不会把刚加入队列的下一层节点也给弹出来。'''''' while queue: level_size = len(queue) current_level = []''''''step3：节点处理内循环 (for _ in range(level_size))从队头取出一个节点 node。记录它的值到 current_level 。如果它有左孩子或右孩子，就把它们送入队尾。它们会在下一轮 while 循环中作为新的一层被处理。'''''' for _ in range(level_size): node = queue.popleft() current_level.append(node.val) # 将下一层节点加入队列 if node.left: queue.append(node.left) [cite: 118] if node.right: queue.append(node.right) [cite: 119] result.append(current_level) return result
举个例子便于各位同学理解
最终输出：[[1], [2, 3], [4, 5, 6], [7]]
3.下面给出几个例题
（1）LeetCode 102 - 二叉树的层序遍历
题目：从上到下、从左到右返回节点值 。
思路：就是上面的那个“模板”
（2）LeetCode 107 - 层序遍历 II
（3）LeetCode 637 - 二叉树的层平均值
# 在 for 循环外初始化 sum = 0 [cite: 199]# 循环内：current_sum += node.val [cite: 203]# 循环结束：result.append(current_sum / size) [cite: 205]
（4）LeetCode 515 - 在每个树行中找最大值
max_val = float('-inf') # 每层初始化 max_val = max(max_val, node.val)
（5）LeetCode 116 - 填充每个节点的下一个右侧节点指针
prev = None for i in range(size): node = queue.popleft() if prev: prev.next = node # 核心连接动作 [cite: 291] prev = node # 更新 prev [cite: 293]
那今天的分享就到这里了，因为项目的原因，每周应该会学三四天，有时间的话每次学完都会更新，有需求的同学可以扫码关注一下哦
