L2-035 完全二叉树的层序遍历测试点

### 完全二叉树的层序遍历 完全二叉树是一种特殊的二叉树结构，除了最后一层外，其他每一层都被完全填充，并且所有的节点都尽可能靠左排列。对于这种类型的二叉树，层序遍历通常采用广度优先搜索（BFS）来实现。 #### 层序遍历的定义 层序遍历是指按照从上到下、从左到右的方式依次访问二叉树中的每一个节点。这种方法可以通过队列数据结构轻松实现[^1]。 #### 实现方法 以下是基于 Python 的一种常见实现方式： ```python from collections import deque class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def levelOrder(root: TreeNode): if not root: return [] result = [] # 存储最终的结果 queue = deque([root]) # 初始化队列 while queue: current_level_size = len(queue) # 当前层的节点数量 current_level_nodes = [] # 存储当前层的节点值 for _ in range(current_level_size): # 处理当前层的所有节点 node = queue.popleft() # 出队 current_level_nodes.append(node.val) # 记录节点值 if node.left: # 如果存在左子节点，则入队 queue.append(node.left) if node.right: # 如果存在右子节点，则入队 queue.append(node.right) result.append(current_level_nodes) # 将当前层的结果加入总结果列表中 return result ``` 上述代码通过 `deque` 数据结构实现了标准的 BFS 过程。每次处理一层时，先记录该层所有节点的值，再将其子节点按顺序加入队列中等待后续处理。 #### 测试用例设计 为了验证算法的有效性和鲁棒性，可以设计如下测试用例： 1. **空树** 输入：无根节点的情况。预期输出为空列表[]。 2. **单节点树** 输入：仅有一个根节点的树。预期输出为[[根节点值]]。 3. **满二叉树** 输入：具有多个层次并完全填充满的二叉树。例如： ```plaintext 1 / \ 2 3 / \ / \ 4 5 6 7 ``` 预期输出为 [[1], [2, 3], [4, 5, 6, 7]]。 4. **不完整的完全二叉树** 输入：某些叶子节点缺失但仍保持左侧对齐特性的树。例如： ```plaintext 1 / 2 / \ 4 5 ``` 预期输出为 [[1], [2], [4, 5]]。 5. **极端情况下的大输入** 输入：接近题目给定的最大规模 N ≤ 30 的完全二叉树实例。确保程序能够高效运行而不超时或溢出内存。 #### 关于 L2-035 的具体说明 虽然未提供关于 L2-035 的详细描述，但从上下文中推测它可能涉及类似的二叉树重建与遍历操作。如果需要进一步扩展功能至更复杂的场景，请参考引用[2] 中提到的方法——即利用后序和中序遍历来重构原始二叉树后再执行相应的层序遍历逻辑[^2]。 --- ###