企业官网建设流程全解析

LeetCode 103. 二叉树的锯齿形层序遍历

思路

在标准层序遍历（BFS）基础上，增加一个方向标志 leftToRight：

· true：从左到右，正常顺序
· false：从右到左，把当前层结果反转

每处理完一层，翻转方向标志即可。

解法一：BFS + 按需反转（最直观）

classSolution{publicList<List<Integer>>zigzagLevelOrder(TreeNoderoot){List<List<Integer>>res=newArrayList<>();if(root==null)returnres;Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);booleanleftToRight=true;while(!queue.isEmpty()){intsize=queue.size();List<Integer>level=newArrayList<>(size);for(inti=0;i<size;i++){TreeNodenode=queue.poll();level.add(node.val);if(node.left!=null)queue.offer(node.left);if(node.right!=null)queue.offer(node.right);}if(!leftToRight){Collections.reverse(level);// 奇数层反转}res.add(level);leftToRight=!leftToRight;// 切换方向}returnres;}}

解法二：BFS + 双端队列（避免反转）

用 Deque 直接控制插入方向，无需最后反转，效率略高。

classSolution{publicList<List<Integer>>zigzagLevelOrder(TreeNoderoot){List<List<Integer>>res=newArrayList<>();if(root==null)returnres;Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);booleanleftToRight=true;while(!queue.isEmpty()){intsize=queue.size();Deque<Integer>level=newArrayDeque<>();for(inti=0;i<size;i++){TreeNodenode=queue.poll();if(leftToRight){level.addLast(node.val);// 从左到右：尾部加入}else{level.addFirst(node.val);// 从右到左：头部加入}if(node.left!=null)queue.offer(node.left);if(node.right!=null)queue.offer(node.right);}res.add(newArrayList<>(level));leftToRight=!leftToRight;}returnres;}}

示例走查

3 / \ 9 20 / \ 15 7

层 方向 原始层节点 输出
0 左→右 [3] [3]
1 右→左 [9, 20] [20, 9]
2 左→右 [15, 7] [15, 7]

结果：[[3], [20, 9], [15, 7]] ✅

复杂度

解法 时间 空间
BFS + reverse O(n) O(n)
BFS + Deque O(n) O(n)

n 为节点总数。空间主要来自结果列表和队列，队列最大为树的最宽一层。

关键点

1. size = queue.size() 必须在 for 循环前取，否则会把下一层节点混入当前层。
2. 方向标志每层结束后取反：leftToRight = !leftToRight。
3. 用 ArrayDeque 替代 LinkedList 做队列性能更好，但 ArrayDeque 不允许 null，本题存 TreeNode 没问题。