Leetcode 103: 二叉树的锯齿形层序遍历
Leetcode 103: 二叉树的锯齿形层序遍历
问题描述：
给定一个二叉树，返回其节点值的锯齿形层序遍历（即第一层从左到右，第二层从右到左，第三层从左到右，依此类推）。
适合面试的解法：广度优先搜索 + 双端队列
解法特点：
- 广度优先搜索（BFS）： 通过层序遍历按层处理节点，确保节点遍历的层次性。
- 双端队列（Deque）： 通过双端队列控制节点值的加入顺序，实现锯齿形效果。
- 从左到右：直接将节点值加入队列的尾部。
- 从右到左：将节点值插入队列的头部。
- 用 BFS 控制每层的遍历顺序，用双端队列处理结果的锯齿形排序。
适合面试的原因：
- 时间复杂度 (O(n))，空间复杂度 (O(n))，效率高且易于实现。
- 展现了灵活的队列操作，是树和 BFS 综合应用的常见场景。
解法思路
核心步骤：
-
初始化：
- 使用队列
Queue<TreeNode>来管理每层的节点。 - 定义标志变量
leftToRight用来判断当前层的遍历方向。
- 使用队列
-
层序遍历：
- 遍历每一层节点：
- 如果
leftToRight = true，将节点值加入到当前层结果的尾部； - 如果
leftToRight = false，将节点值插入到当前层结果的头部。
- 如果
- 将当前层的结果加入最终结果列表。
- 遍历每一层节点：
-
翻转方向：
- 每处理完一层后，翻转
leftToRight，切换从左到右或从右到左的方向。
- 每处理完一层后，翻转
代码模板
方法：广度优先搜索 + 双端队列
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result; // 如果树为空，直接返回空列表
Queue<TreeNode> queue = new LinkedList<>(); // BFS 队列
queue.offer(root);
boolean leftToRight = true; // 初始遍历方向是从左到右
while (!queue.isEmpty()) {
int levelSize = queue.size();
Deque<Integer> levelList = new LinkedList<>(); // 双端队列存储当前层的节点值
// 遍历当前层所有节点
for (int i = 0; i < levelSize; i++) {
TreeNode currentNode = queue.poll();
if (leftToRight) {
levelList.addLast(currentNode.val); // 从左到右：添加到尾部
} else {
levelList.addFirst(currentNode.val); // 从右到左：添加到头部
}
// 加入下一层的节点
if (currentNode.left != null) queue.offer(currentNode.left);
if (currentNode.right != null) queue.offer(currentNode.right);
}
// 将当前层的结果加入最终结果
result.add(new ArrayList<>(levelList));
// 翻转方向
leftToRight = !leftToRight;
}
return result;
}
}
代码详细注释
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
// 定义最终结果列表
List<List<Integer>> result = new ArrayList<>();
// 特殊边界条件：如果树为空，直接返回
if (root == null) return result;
// 初始化 BFS 队列和方向标记
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root); // 将根节点加入 BFS 队列
boolean leftToRight = true; // 起始从左到右遍历
// BFS 遍历二叉树的每一层
while (!queue.isEmpty()) {
int levelSize = queue.size(); // 当前层的节点数
Deque<Integer> levelList = new LinkedList<>(); // 使用双端队列保存当前层结果
for (int i = 0; i < levelSize; i++) {
TreeNode currentNode = queue.poll(); // 从队列中取出当前节点
// 根据遍历方向将节点值添加到双端队列
if (leftToRight) {
levelList.addLast(currentNode.val); // 从左到右时，添加到队尾
} else {
levelList.addFirst(currentNode.val); // 从右到左时，添加到队头
}
// 将当前节点的左右孩子加入队列
if (currentNode.left != null) {
queue.offer(currentNode.left);
}
if (currentNode.right != null) {
queue.offer(currentNode.right);
}
}
// 将双端队列的结果转换为列表，加入最终结果
result.add(new ArrayList<>(levelList));
// 翻转方向
leftToRight = !leftToRight;
}
return result; // 返回最终结果
}
}
复杂度分析
时间复杂度：
- 每个节点仅被访问一次，时间复杂度为 (O(n))，其中 (n) 是树中节点总数。
空间复杂度：
- BFS 队列最多存储一层的节点，最坏情况是 (O(n))。
- 使用双端队列临时存储每层结果，复杂度为 (O(w))，其中 (w) 是二叉树的最大宽度。
综合空间复杂度为 (O(n))。
测试用例
示例 1：
输入:
3
/ \
9 20
/ \
15 7
输出:
[
[3],
[20,9],
[15,7]
]
示例 2：
输入:
1
/ \
2 3
/ \
4 5
输出:
[
[1],
[3,2],
[4,5]
]
示例 3：
输入: null
输出: []
如何快速 AC（面试技巧）
1. 清晰解释 BFS 对二叉树的层序遍历
- BFS 利用队列按层层处理节点，巧妙地分离层次关系。
- 在片段中添加「左右翻转」是实现锯齿形遍历的核心技巧。
2. 灵活使用双端队列
- 明确说明为什么使用双端队列：
- 从左到右时添加到队尾；
- 从右到左时插入到队头。
3. 时间和空间复杂度分析
- 说明 BFS 遍历节点的线性开销 (O(n))，无多余操作，非常高效。
4. 特殊情况处理
- 空树（根节点为 null）时，应返回空结果。
总结
适合面试的解法：广度优先搜索 + 双端队列
- 女人拆分思路：利用 BFS 分层处理节点，用双端队列处理锯齿效果。
- 时间复杂度 (O(n))、空间复杂度 (O(n))，是最优解决方案。
如何快速 AC：
- 清晰实现 BFS，按层处理树节点；
- 双端队列解决锯齿效果，结合方向标记灵活转换；
- 完整测试，涵盖空树和各种复杂结构树。
这种高效解法逻辑清晰，非常适合面试场景！