二叉树的锯齿形层序遍历（Zigzag Level Order Traversal） 题目描述 给定一个二叉树的根节点 root ，返回其节点值的锯齿形层序遍历结果（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 示例 输入： root = [3,9,20,null,null,15,7] 输出： [[3],[20,9],[15,7]] 解释： 第 1 层从左到右： [3] 第 2 层从右到左： [20,9] 第 3 层从左到右： [15,7] 解题步骤 1. 问题分析 锯齿形层序遍历本质是层序遍历的变种，需要按层处理节点，但奇数层（从 0 开始计数）从左到右输出，偶数层从右到左输出。关键点在于： 层序遍历需要队列（或双端队列）辅助。 通过标志位控制每层的输出方向。 2. 基础思路：层序遍历框架 使用队列进行标准的层序遍历（BFS）： 将根节点入队。 当队列不为空时，处理当前层的所有节点： 记录当前层的节点数（队列长度）。 依次出队节点，将其值存入当前层的结果列表。 将节点的左右子节点入队。 3. 添加锯齿形逻辑 设置一个标志位 left_to_right （初始为 True ），表示当前层的输出方向。 当前层节点值收集完成后，根据标志位决定是否反转该层列表： 若 left_to_right 为 True ，直接添加当前层列表。 若为 False ，则反转当前层列表后再添加。 每处理完一层，反转标志位 left_to_right = not left_to_right 。 4. 优化：双端队列（Deque）避免反转操作 使用双端队列可以在添加节点值时直接控制顺序，避免最后反转列表： 若当前层从左到右，则从队列尾部添加节点值。 若当前层从右到左，则从队列头部添加节点值（实现逆序）。 5. 算法步骤（使用双端队列） 初始化队列 queue 和结果列表 result ，将根节点入队。 设置方向标志 left_to_right = True 。 当队列不为空： 初始化双端队列 deque 存储当前层节点值。 获取当前层节点数量 level_size 。 遍历当前层每个节点： 出队一个节点 node 。 若 left_to_right 为 True ，将 node.val 添加到 deque 尾部。 若为 False ，将 node.val 添加到 deque 头部。 将 node 的左右子节点按顺序入队。 将 deque 转换为列表并加入 result 。 反转标志位： left_to_right = not left_to_right 。 返回 result 。 6. 复杂度分析 时间复杂度：O(N)，每个节点访问一次。 空间复杂度：O(N)，队列存储节点。 7. 关键点总结 锯齿形遍历的核心是 按层处理 与 方向交替 。 双端队列优化了顺序控制，避免显式反转列表。 注意处理空树（ root 为 null ）的特殊情况。