二叉搜索树（BST）的层序遍历与按层存储

题目描述
给定一个二叉搜索树（BST）的根节点，要求对该树进行层序遍历（广度优先遍历），并将每一层的节点值分别存储在一个子列表中，最终返回一个列表的列表，其中每个子列表对应树的一层节点值。

例如，给定树：

      5
     / \
    3   8
   / \   \
  2   4   9

应返回：
[[5], [3, 8], [2, 4, 9]]

这道题考察对BST（或一般二叉树）的层序遍历的熟练实现，以及如何在遍历过程中区分不同层级。

解题过程循序渐进讲解

步骤1：理解层序遍历的核心思想
层序遍历从根节点开始，逐层访问节点，先访问离根节点最近的层（第0层），然后逐层向下。这天然适合使用队列（先进先出）来实现：

1. 初始化队列，将根节点入队。
2. 当队列不为空时：
   • 弹出队首节点，访问它。
   • 如果该节点有左子节点，左子节点入队。
   • 如果该节点有右子节点，右子节点入队。

但这里需要按层分开存储，所以需要知道当前层有多少个节点。

步骤2：如何在遍历时区分不同层
一种常见的方法是：在每一层开始前，记录当前队列中的节点数（这就是当前层的节点数），然后依次处理这些节点，并将它们的子节点入队。处理完这一批节点后，下一批节点就是下一层。

具体步骤：

1. 初始化一个队列，将根节点入队（如果根节点不为空）。
2. 初始化结果列表 result = []。
3. 当队列不为空时：
   • 获取当前队列的大小 level_size（这就是当前层的节点数）。
   • 初始化一个空列表 current_level，用于存储当前层的节点值。
   • 循环 level_size 次：
     • 弹出队首节点。
     • 将节点值加入 current_level。
     • 如果该节点有左子节点，左子节点入队。
     • 如果该节点有右子节点，右子节点入队。
   • 将 current_level 加入 result。
4. 返回 result。

步骤3：举例推演
以示例树为例：

      5
     / \
    3   8
   / \   \
  2   4   9

初始化：queue = [5], result = []

• 第1轮（第0层）：
  • level_size = 1（队列中有1个节点：5）
  • current_level = []
  • 弹出5，current_level = [5]，左子3入队，右子8入队
  • 队列变为 [3, 8]
  • 将 [5] 加入 result，此时 result = [[5]]
• 第2轮（第1层）：
  • level_size = 2（队列中有2个节点：3, 8）
  • current_level = []
  • 弹出3，current_level = [3]，左子2入队，右子4入队
  • 弹出8，current_level = [3, 8]，右子9入队
  • 队列变为 [2, 4, 9]
  • 将 [3, 8] 加入 result，此时 result = [[5], [3, 8]]
• 第3轮（第2层）：
  • level_size = 3（队列中有3个节点：2, 4, 9）
  • current_level = []
  • 依次弹出2, 4, 9，它们都没有子节点，所以 current_level = [2, 4, 9]，队列变空
  • 将 [2, 4, 9] 加入 result，此时 result = [[5], [3, 8], [2, 4, 9]]
• 队列为空，结束。

步骤4：代码实现（Python示例）

from collections import deque

def 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 result

时间复杂度：O(n)，每个节点入队、出队一次。
空间复杂度：O(n)，队列中最多存储一层的节点，最坏情况是完美二叉树的最底层，约有 n/2 个节点。

步骤5：扩展思考

1. 如果要求从底层向上输出（即自底向上层序遍历），只需在最后将 result 反转即可。
2. 二叉搜索树（BST）的性质在此题中并未特别利用，该解法适用于任何二叉树。
3. 递归解法：也可以用DFS递归，在递归时记录当前层数，将节点值加入对应层的列表。但递归不是严格的广度优先，而是深度优先，只是按层收集值。