算法练习（力扣-BFS）——102. 二叉树的层序遍历

题目描述（简要概括）

题目链接：102. 二叉树的层序遍历 - 力扣（LeetCode）

题目要求对给定的二叉树进行层序遍历（从上到下，从左到右），并返回遍历的结果。层序遍历是一种基于广度优先搜索（BFS）的遍历方式，通常使用队列来实现。

输入输出

• 输入：二叉树的根节点 root。

• 输出：一个二维列表，表示每一层的节点值。

解题思路

1. 使用队列实现 BFS：

   • 初始化一个队列，将根节点加入队列。

   • 每次从队列中取出一层的节点，记录它们的值，并将它们的子节点加入队列。

   • 重复上述过程，直到队列为空。

2. 记录每一层的节点值：

   • 使用一个列表来存储每一层的节点值。

   • 最终将所有层的节点值组合成一个二维列表作为结果。

---

代码详细解析

from collections import dequeclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef list_to_tree(data):if not data:return Noneroot = TreeNode(data[0])queue = [root]index = 1while queue and index < len(data):node = queue.pop(0)if index < len(data) and data[index] is not None:node.left = TreeNode(data[index])queue.append(node.left)index += 1if index < len(data) and data[index] is not None:node.right = TreeNode(data[index])queue.append(node.right)index += 1return rootdef levelOrder(root):if not root:return []result = []queue = deque([root])while queue:level_size = len(queue)current_level = []for _ in range(level_size):node = queue.popleft()current_level.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)result.append(current_level)return resultif __name__ == "__main__":data = [3, 9, 20, None, None, 15, 7]root = list_to_tree(data)result = levelOrder(root)print(result)  # 输出：[[3], [9, 20], [15, 7]]

---

示例解析

假设输入的二叉树如下：

复制

    3/ \9  20/  \15   7

1. 初始化：

   • 队列：[3]

   • 结果：[]

2. 第一层（根节点）：

   • 当前层：[3]

   • 队列：[9, 20]

   • 结果：[[3]]

3. 第二层：

   • 当前层：[9, 20]

   • 队列：[15, 7]

   • 结果：[[3], [9, 20]]

4. 第三层：

   • 当前层：[15, 7]

   • 队列：[]

   • 结果：[[3], [9, 20], [15, 7]]

5. 返回结果：

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

---

总结

通过使用队列实现 BFS，我们可以轻松地完成二叉树的层序遍历。每层的节点值按顺序加入结果列表，最终返回一个二维列表。希望这个解析对你有帮助！如果有任何问题，欢迎随时提问。