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

题目描述

返回二叉树的锯齿形层序遍历：第一层从左到右，第二层从右到左，之后交替方向。

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

题型判断

节点的访问顺序仍然是标准 BFS。变化的只是每层结果的写入方向。

也就是说，队列仍然负责按层、从左到右访问节点；锯齿形只影响当前层结果数组的写入位置。不要为了反向输出而改变孩子的入队顺序，否则容易破坏下一层的正常结构。

核心思路

使用 leftToRight 表示当前层方向。每层创建一个长度为 levelSize 的数组：

从左到右时，节点值写到下标 i。
从右到左时，节点值写到下标 levelSize - 1 - i。

这样既不需要反转数组，也不需要在数组头部插入元素。

levelSize - 1 是当前层数组的最后一个下标。levelSize - 1 - i 表示从最后一个位置开始写，随着 i 增大，写入位置一步步向左移动。

例如当前层按 BFS 访问到的节点是 [9, 20]，levelSize = 2。

从右到左写入：
i = 0，节点 9  写到下标 1
i = 1，节点 20 写到下标 0

最终得到 [20, 9]

关键点是：访问顺序不变，写入位置改变。

代码实现

var zigzagLevelOrder = function (root) {
  if (!root) return [];

  const result = [];
  const queue = [root];
  let head = 0;
  let leftToRight = true;

  while (head < queue.length) {
    const levelSize = queue.length - head;
    const level = new Array(levelSize);

    for (let i = 0; i < levelSize; i++) {
      const node = queue[head++];
      const index = leftToRight ? i : levelSize - 1 - i;
      level[index] = node.val;

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(level);
    leftToRight = !leftToRight;
  }

  return result;
};

复杂度分析

时间复杂度：O(n)，每个节点只会被访问一次。
空间复杂度：O(n)。

当前实现使用 head 指针模拟出队，queue 中访问过的节点不会被删除，最坏情况下会保存所有节点。如果使用真正的队列结构，只看遍历过程中的待处理节点，辅助空间可以理解为 O(w)，其中 w 是二叉树最大层宽。计入返回结果时一定是 O(n)。

边界与易错点

空树返回 []。
始终按“左孩子、右孩子”入队，方向只影响结果下标。
使用 unshift() 会反复移动数组元素，宽层情况下效率较差。
leftToRight 要在每一层结束后切换，不能在处理每个节点时切换。
使用 head 指针时，循环条件应该是 head < queue.length，不能只判断 queue.length > 0。
不要根据当前方向改变左右孩子的入队顺序。队列负责维持标准层序结构，如果一会儿左孩子先入队、一会儿右孩子先入队，下一层节点的相对顺序会被打乱。

ON THIS PAGE

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

#题目描述

#题型判断

#核心思路

#代码实现

#复杂度分析