0103.二叉树的锯齿形层序遍历
难度：🟡 中等
标签：树、广度优先搜索、二叉树、队列
题目描述
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
示例 2：
输入：root = [1]
输出：[1](./1.md)
示例 3：
输入：root = []
输出：[]
解题思路
核心思想
本题是标准层序遍历的一个变种。核心思想仍然是使用 广度优先搜索（BFS） 来逐层访问节点，但不同之处在于，我们需要根据层级的奇偶性来决定该层节点的存储顺序。一层从左到右，下一层从右到左，交替进行。
思路选择
最适合的思路是 广度优先搜索（BFS）+ 双端队列（Deque）或方向标记。 我们可以使用一个标准的队列来进行 BFS，但在将每层节点存入结果数组时，通过一个表示方向的标记（或直接根据层级的索引）来决定是从数组头部插入（unshift）还是从尾部插入（push）。
偶数层 (0, 2, 4...)：从左到右遍历，将节点值
push到层结果数组的末尾。奇数层 (1, 3, 5...)：从右到左遍历，将节点值
unshift到层结果数组的头部。
这样就巧妙地实现了锯齿形的输出效果，而无需在每层遍历结束后再进行翻转操作。
关键步骤
边界处理：如果根节点
root为空，直接返回空数组[]。初始化：创建一个队列
queue并将根节点入队。创建一个结果数组results。初始化一个层级索引levelIndex = 0。开始循环：当
queue不为空时，持续循环。分层处理： a. 在循环开始时，记录当前
queue的长度levelSize，这代表当前层级的节点总数。 b. 创建一个临时的层结果数组currentLevel。 c. 启动一个内层循环，执行levelSize次。 d. 在内层循环中，从queue的头部取出一个节点（出队）。 e. 根据层级奇偶性插入：如果levelIndex是偶数，则currentLevel.push(node.val)；如果是奇数，则currentLevel.unshift(node.val)。 f. 如果该节点有非空的左、右子节点，依次将其入队。存储与更新：内层循环结束后，
currentLevel就包含了当前层按锯齿形顺序排列的节点值。将其推入results数组，并将levelIndex加一。返回结果：当外层
while循环结束时，返回results。
代码实现
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var zigzagLevelOrder = function(root) {
if (!root) {
return [];
}
const queue = [root];
const results = [];
let isOrderLeft = true; // true: 从左到右, false: 从右到左
while (queue.length > 0) {
const levelSize = queue.length;
const currentLevel = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
// 根据方向决定从头部还是尾部插入
if (isOrderLeft) {
currentLevel.push(node.val);
} else {
currentLevel.unshift(node.val);
}
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
results.push(currentLevel);
isOrderLeft = !isOrderLeft; // 反转下一层的方向
}
return results;
};
复杂度分析
时间复杂度：O(n) 其中 n 是树中节点的总数。每个节点都会被访问一次。虽然
unshift操作在数组中理论上是 O(k)，但由于每层总共处理 k 个节点，均摊下来，整个算法的时间复杂度依然是线性的 O(n)。空间复杂度：O(w) 其中 w 是树的最大宽度。空间复杂度主要由队列的存储决定，最坏情况下会存储树最宽一层的所有节点。
相关题目
总结
本题是对标准层序遍历的巧妙扩展。通过在 BFS 过程中引入一个方向标记，并在构建每层结果时利用 push 和 unshift 的不同特性，可以优雅地实现锯齿形的输出，而无需对中间结果进行额外的反转操作，体现了算法设计的灵活性。