1.思路：要求二叉树的层序遍历的打印顺序交替变化。考虑层序遍历 + 双端队列。 利用双端队列的两端皆可添加元素的特性，设打印列表（双端队列）tmp，并规定：
（1）偶数层（第0层也是偶数层）：从左到右正常顺序。
（2）奇数层：从右到左反转顺序。
2.过程：
（1）特例处理：当树的根节点为空时，直接返回空列表[]。
（2）初始化：打印结果空列表res，包含根节点的双端队列deque。
（3）BFS循环：当deque为空时跳出。
（a）新建列表tmp，用于临时存储当前层的打印结果。
（b）当前层循环打印：循环次数为当前层的节点数（即deque的长度）。
——出队：队首元素出队，记为node。
——打印：若为奇数层，将node.val添加至tmp尾部；否则，添加至tmp头部。
——添加子节点：若node的左（右）子节点不为空，则加入deque。
（c）将当前层的结果tmp转化为list并添加入res。
（4）返回值：返回打印结果列表res即可。
复杂度分析：
（1）时间复杂度：O(n)，其中n为二叉树的节点数量，即BFS需要循环n次，占用O(n)。双端队列的队首和队尾的添加和删除操作的时间复杂度均为O(1)。
（2）空间复杂度：O(n)，最差情况下，即当树为满二叉树时，最多有n/2个树节点同时在deque中，使用O(n)大小的额外空间。
附代码：
class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { LinkedList<TreeNode> queue = new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); if (root != null){ queue.add(root); } while (!queue.isEmpty()) { LinkedList<Integer> tmp = new LinkedList<>(); // 倒序遍历的作用是从循环开始时快照当前层的节点数量 // 然后只处理这个固定数量的节点 // 避免把新加入的下一层节点错误地当作当前层处理 for(int i = queue.size();i > 0;i--) { TreeNode node = queue.remove(); if (res.size() % 2 == 0) tmp.addLast(node.val); else tmp.addFirst(node.val); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } res.add(tmp); } return res; } }ACM模式：
import java.util.Scanner; import java.util.ArrayList; import java.util.List; import java.util.LinkedList; // 定义二叉树节点类 class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; this.left = null; this.right = null; } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取输入的一行，并去除首尾空格 String input = scanner.nextLine().trim(); // 构建二叉树 TreeNode root = buildTree(input); // 获取锯齿形层序遍历结果 Solution solution = new Solution(); List<List<Integer>> result = solution.zigzagLevelOrder(root); // 输出结果：每层占一行，节点之间用空格分隔 for (List<Integer> level : result) { for (int j = 0; j < level.size(); j++) { System.out.print(level.get(j)); if (j < level.size() - 1) { System.out.print(" "); } } System.out.println(); } scanner.close(); } // 根据输入字符串构建二叉树（层序遍历格式，null表示空节点） private static TreeNode buildTree(String input) { if (input == null || input.length() == 0) { return null; } String[] values = input.split(" "); if (values.length == 0 || values[0].equals("null")) { return null; } TreeNode root = new TreeNode(Integer.parseInt(values[0])); LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); int i = 1; while (!queue.isEmpty() && i < values.length) { TreeNode current = queue.remove(); // 处理左子节点 if (i < values.length && !values[i].equals("null")) { current.left = new TreeNode(Integer.parseInt(values[i])); queue.add(current.left); } i++; // 处理右子节点 if (i < values.length && !values[i].equals("null")) { current.right = new TreeNode(Integer.parseInt(values[i])); queue.add(current.right); } i++; } return root; } } // 解题类，包含锯齿形层序遍历的方法 class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { LinkedList<TreeNode> queue = new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); if (root != null) { queue.add(root); } while (!queue.isEmpty()) { LinkedList<Integer> tmp = new LinkedList<>(); // 倒序遍历的作用是从循环开始时快照当前层的节点数量 // 然后只处理这个固定数量的节点 // 避免把新加入的下一层节点错误地当作当前层处理 for (int i = queue.size(); i > 0; i--) { TreeNode node = queue.remove(); if (res.size() % 2 == 0) { tmp.addLast(node.val); } else { tmp.addFirst(node.val); } if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } res.add(tmp); } return res; } }
