力扣链接：103.二叉树的锯齿形层序遍历

难度：⭐⭐

解题关键词：二叉树、层序遍历、队列

解题思路：在二叉树平常的层序遍历上，增加一个层数的 flag，如果是奇数行，那么从左到右输出，否则从右到左输出结果。

function zigzagLevelOrder(root: TreeNode | null): number[][] {
  // 如果 root 为空，直接返回空数组
  if (root === null) return [];

  // 队列
  const queue: TreeNode[] = [root];
  // 结果
  const result: number[][] = [];

  let layer = 1;

  // 当队列不为空时
  while (queue.length) {
    // 保存当前层级的 node 个数
    let size = queue.length;

    // 当前层级的 node 值
    const curLayerNodeValues: number[] = [];
    while (size--) {
      // 出队
      const node = queue.shift();
      curLayerNodeValues.push(node.val);

      // 左节点
      if (node.left) queue.push(node.left);
      // 右节点
      if (node.right) queue.push(node.right);
    }

    // 奇数行 - 从左到右输出
    // 偶数行 - 从右到左输出
    result.push(
      layer % 2 === 1 ? curLayerNodeValues : curLayerNodeValues.reverse()
    );
    // 层数 ++
    layer++;
  }

  return result;
}