二叉树的锯齿形层次遍历（Zigzag Level Order Traversal）

题目描述
给定一个二叉树的根节点，返回其节点值的锯齿形层次遍历结果。即先从左往右遍历当前层，下一层则从右往左遍历，再下一层又从左往右，以此类推，层与层之间交替进行方向变化。

解题过程

1. 问题分析
锯齿形层次遍历是在普通层次遍历（BFS）基础上的变体。普通BFS使用队列，每层按固定方向（从左到右）遍历。而锯齿形遍历需要在不同层改变方向：

• 偶数层（0-based索引）：从左到右
• 奇数层：从右到左
• 需要记录当前层数或通过标志位控制方向

2. 核心思路
使用广度优先搜索（BFS）框架，但需要：

• 记录当前层数（或使用布尔标志）
• 根据层数奇偶性决定当前层节点的输出顺序
• 可以使用双端队列（deque）或普通队列+列表反转优化

3. 方法一：BFS + 层列表反转
这是最直观的实现方式：

步骤详解：

1. 初始化队列（存储待处理节点）和结果列表
2. 将根节点入队（如果根非空）
3. 设置方向标志位（如left_to_right = True）
4. 当队列不为空时：
   a. 获取当前层的节点数量level_size
   b. 创建当前层的值列表current_level
   c. 遍历当前层所有节点：
   • 出队一个节点
   • 将节点值加入current_level
   • 将节点的左右子节点入队（如果存在）
     d. 如果当前方向应为从右到左（即left_to_right为False），则反转current_level
     e. 将current_level加入结果列表
     f. 切换方向标志位（left_to_right = !left_to_right）

代码示例（Python风格伪代码）：

def zigzagLevelOrder(root):
    if not root:
        return []
    
    result = []
    queue = collections.deque([root])
    left_to_right = True  # 方向标志
    
    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)
        
        # 根据方向决定是否反转当前层
        if not left_to_right:
            current_level.reverse()
        
        result.append(current_level)
        left_to_right = not left_to_right  # 切换方向
    
    return result

4. 方法二：双端队列（Deque）优化
避免反转操作，通过双端队列的不同操作实现方向控制：

步骤详解：

1. 使用双端队列，根据当前方向决定：
   • 从左到右时：从队列前端出队，子节点按从左到右顺序加入队尾
   • 从右到左时：从队列后端出队，子节点按从右到左顺序加入队首
2. 需要记录当前层节点及其处理顺序

代码示例：

def zigzagLevelOrder(root):
    if not root:
        return []
    
    result = []
    deque = collections.deque([root])
    left_to_right = True
    
    while deque:
        level_size = len(deque)
        current_level = []
        
        if left_to_right:
            # 从左到右处理
            for _ in range(level_size):
                node = deque.popleft()
                current_level.append(node.val)
                # 子节点按左右顺序加入队尾
                if node.left:
                    deque.append(node.left)
                if node.right:
                    deque.append(node.right)
        else:
            # 从右到左处理
            for _ in range(level_size):
                node = deque.pop()
                current_level.append(node.val)
                # 子节点按右左顺序加入队首（注意顺序）
                if node.right:
                    deque.appendleft(node.right)
                if node.left:
                    deque.appendleft(node.left)
        
        result.append(current_level)
        left_to_right = not left_to_right
    
    return result

5. 复杂度分析

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

6. 关键点总结

• 锯齿形遍历本质是BFS的变体，核心在于方向交替
• 方法一更直观易懂，方法二性能稍优（避免反转操作）
• 注意处理空树的情况
• 保持层次结构清晰，确保每层节点被正确处理

这种方法在面试中考察对BFS的灵活运用和对数据结构的理解深度。