树与图中等1 种解法
#103二叉树的锯齿形层序遍历
逐层遍历二叉树，并交替使用从左到右、从右到左的输出顺序。
#二叉树#广度优先搜索#双端队列
原题
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[20,9],[15,7]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -100 <= Node.val <= 100
解题主线
- 节点扩展始终保持左后右，只有当前层结果的插入方向需要切换。
解法 1：BFS 与双端队列
奇数层尾插、偶数层头插节点值。
-
时间复杂度： O(n)
-
空间复杂度： O(w)
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
boolean leftToRight = true;
while (!queue.isEmpty()) {
// 固定当前层节点数，避免下一层新入队节点被提前处理
int size = queue.size();
Deque<Integer> level = new ArrayDeque<>();
for (int i = 0; i < size; i++) {
TreeNode node = 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);
}
result.add(new ArrayList<>(level));
// 每完成一层再翻转下一层的输出方向
leftToRight = !leftToRight;
}
return result;
}
}边界与易错点
- 不要同时反转子节点入队方向，否则容易破坏下一层的自然顺序。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/tree/Q103_btree_zigzagLevelOrder.java