二叉树的锯齿形层序遍历

题目描述：给定一个二叉树的根节点，返回其节点值的锯齿形层序遍历。即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行。

解题思路：

1. 基本思路基于二叉树的层序遍历（BFS），使用队列辅助
2. 关键点在于记录当前层数，根据层数的奇偶性决定遍历方向
3. 偶数层（从0开始计数）从左到右，奇数层从右到左
4. 可以通过反转列表或双端队列实现方向控制

详细步骤：

步骤1：基础层序遍历框架

• 使用队列进行标准的BFS层序遍历
• 每次处理一层的所有节点
• 记录当前层的节点值列表

步骤2：添加方向控制

• 设置一个标志位（如level）记录当前层数
• 当level为偶数时，按正常顺序添加节点值
• 当level为奇数时，按逆序添加节点值（或从尾部插入）

步骤3：具体实现方法
方法一：列表反转法

1. 进行标准层序遍历，每层按从左到右顺序收集节点值
2. 遇到奇数层时，将该层的节点值列表反转
3. 将处理后的列表加入结果集

方法二：双端队列法

1. 使用双端队列（deque）存储每层节点值
2. 偶数层：从队列尾部插入节点值（正常顺序）
3. 奇数层：从队列头部插入节点值（实现逆序）

代码实现（列表反转法）：

from collections import deque

def zigzagLevelOrder(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    level = 0  # 记录当前层数，从0开始
    
    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 level % 2 == 1:  # 奇数层，需要反转
            current_level.reverse()
        
        result.append(current_level)
        level += 1  # 进入下一层
    
    return result

复杂度分析：

• 时间复杂度：O(n)，每个节点访问一次
• 空间复杂度：O(n)，队列和结果集的空间开销

关键要点：

1. 层序遍历是基础，方向控制是核心
2. 注意处理空树的边界情况
3. 层数计数从0开始，便于使用模2判断奇偶性
4. 两种实现方法的时间复杂度相同，可根据具体需求选择

这种锯齿形遍历在需要交替显示数据的场景中很实用，如某些UI布局和数据分析可视化。