实现二叉树的层序遍历

题目描述
二叉树的层序遍历（又称广度优先遍历）要求按层级顺序遍历二叉树节点，从根节点开始，逐层从左到右访问每个节点。这是二叉树遍历中最基础且重要的算法之一。

解题思路
层序遍历的核心思想是使用队列（FIFO结构）来维护待访问的节点顺序：

1. 将根节点入队
2. 循环执行以下步骤直到队列为空：
   • 出队一个节点并访问
   • 将该节点的左子节点入队（如果存在）
   • 将该节点的右子节点入队（如果存在）

详细步骤分解

1. 基础层序遍历（返回一维数组）

def levelOrder(root):
    if not root:
        return []
    
    result = []
    queue = collections.deque([root])  # 初始化队列
    
    while queue:
        node = queue.popleft()  # 出队
        result.append(node.val)  # 访问节点值
        
        # 将子节点入队
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result

2. 分层输出的层序遍历（返回二维数组）

def levelOrder(root):
    if not root:
        return []
    
    result = []
    queue = collections.deque([root])
    
    while queue:
        level_size = len(queue)  # 当前层的节点数
        level_nodes = []  # 存储当前层的节点值
        
        for _ in range(level_size):
            node = queue.popleft()
            level_nodes.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level_nodes)  # 将当前层加入结果
    
    return result

3. Z字形层序遍历（锯齿形遍历）

def zigzagLevelOrder(root):
    if not root:
        return []
    
    result = []
    queue = collections.deque([root])
    left_to_right = True  # 遍历方向标志
    
    while queue:
        level_size = len(queue)
        level_nodes = [0] * level_size  # 预分配空间
        
        for i in range(level_size):
            node = queue.popleft()
            
            # 根据方向确定插入位置
            index = i if left_to_right else level_size - 1 - i
            level_nodes[index] = node.val
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level_nodes)
        left_to_right = not left_to_right  # 反转方向
    
    return result

复杂度分析

• 时间复杂度：O(n)，每个节点恰好被访问一次
• 空间复杂度：O(n)，队列中最多存储n个节点

关键要点

1. 队列选择：使用双端队列（deque）比列表更高效
2. 分层技巧：在循环开始前记录当前队列长度，即可区分不同层级
3. 边界处理：空树的特殊情况需要单独处理
4. 方向控制：Z字形遍历通过索引计算实现，避免重复反转列表

实际应用场景

• 二叉树的最小深度计算
• 二叉树的右视图/左视图
• 判断完全二叉树
• 构建二叉树的最优策略设计