leetcode102：二叉树的层序遍历

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

步骤1：计算问题性质定义

题目要求对给定的二叉树进行层序遍历，并返回每一层的节点值列表。具体来说：

• 输入：二叉树的根节点 root，它可能为空。
• 输出：一个二维向量，其中每个向量代表二叉树的一层，包含该层所有节点的值。
• 限制：树中节点的数量在范围 [0, 2000] 内，每个节点的值在范围 [-1000, 1000] 内。
• 边界条件：当输入为空树时，应返回一个空列表。

步骤2：解题步骤与算法设计思路

解题步骤如下：

1. 初始化一个队列，将根节点入队。
2. 当队列不为空时，进行以下操作：
   • 记录当前队列的大小，这代表当前层的节点数量。
   • 遍历当前层的所有节点，对于每个节点：
     • 将节点值加入当前层的列表。
     • 如果节点有左子节点，将左子节点入队。
     • 如果节点有右子节点，将右子节点入队。
   • 将当前层的列表加入结果列表。
3. 队列为空时，返回结果列表。

采用的算法设计思路是广度优先搜索（BFS），适用于层序遍历。时间复杂度为 O(N)，其中 N 是树中节点的数量，因为每个节点只被访问一次。空间复杂度也是 O(N)，在最坏情况下，队列可能包含树的所有节点。

步骤3：C++代码实现

步骤4：获得的启发

通过解决这个层序遍历问题，我们可以学习到：

• 如何使用队列实现广度优先搜索。
• 如何处理树形结构的遍历问题。
• 如何在遍历过程中维护不同层级的节点信息。

步骤5：实际应用

在实际生活中，层序遍历算法可以应用于以下场景：

• 在网络路由算法中，计算最短路径或广播消息。
• 在图形界面设计中，处理分层显示的元素，例如在CAD软件中处理图层的显示。
• 在游戏开发中，实现地图的生成和渲染，尤其是在生成等高线图或地形图时。

具体应用示例：

• 网络路由算法：在计算机网络中，层序遍历可以用来实现距离向量路由算法，如距离向量多播路由协议（DVMRP）。实现方法是将网络中的每个路由器视为树中的一个节点，每个路由器的邻居作为子节点。通过层序遍历，路由器可以收集到网络中所有节点的距离信息，从而计算出到达每个节点的最短路径。