二叉树锯齿形层序遍历怎么做？

简化版

锯齿形层序遍历是在普通层序遍历基础上交替改变每层输出方向。常见做法是 BFS 按层遍历，用布尔变量控制本层从左到右还是从右到左，把值插入双端队列，时间 O(n)，空间 O(w)。

详细版

队列仍然保存下一批要访问的节点，层边界仍然通过当前队列大小 size 固定。区别在于收集本层结果时，如果方向是从左到右就尾插，如果从右到左就头插；一层结束后翻转方向。

List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root == null) return ans;
    Queue<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    boolean leftToRight = true;
    while (!q.isEmpty()) {
        int size = q.size();
        Deque<Integer> level = new ArrayDeque<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (leftToRight) level.offerLast(node.val);
            else level.offerFirst(node.val);
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        ans.add(new ArrayList<>(level));
        leftToRight = !leftToRight;
    }
    return ans;
}

不要改变子节点入队顺序，保持左孩子先入队、右孩子后入队即可；方向只影响输出顺序。

完整版教学

一、锯齿形本质仍然是层序遍历

这题容易让人误以为要改变遍历顺序，其实节点访问仍然是从上到下按层推进。锯齿形只是每层结果展示方向不同：第 0 层从左到右，第 1 层从右到左，第 2 层再从左到右。访问顺序和输出顺序分开，代码就简单很多。

      3
     / \
    9  20
      /  \
     15   7

输出: [ [3], [20,9], [15,7] ]

队列里第二层仍然按 9,20 出队，只是收集结果时把值放到双端队列头部，最后展示成 20,9。

二、固定 size 是按层处理的关键

普通 BFS 如果只用 while (!q.isEmpty()) 不记录层大小，就会把不同层混在一起。锯齿形必须知道“这一轮正好处理当前层的所有节点”，所以每轮开始先取 size = q.size()。这一刻队列里有多少节点，当前层就有多少节点。

第 0 层开始: q=[3], size=1
第 1 层开始: q=[9,20], size=2
第 2 层开始: q=[15,7], size=2

处理当前层时加入队列的是下一层节点，但它们不会被本轮处理，因为循环次数已经由 size 固定住了。

三、为什么推荐改输出，不推荐改入队

一种写法是奇偶层改变左右孩子入队顺序，但这样会影响下一层内部顺序，容易绕晕。更稳的写法是始终左孩子先入队、右孩子后入队，把“遍历结构”和“展示方向”拆开。双端队列正好支持头插和尾插，能用 O(1) 完成方向控制。

层方向	子节点入队	值收集方式	说明
从左到右	左后右	`offerLast`	与普通层序一致
从右到左	左后右	`offerFirst`	只反转本层展示
下一层	左后右	根据布尔值	不污染树的访问顺序

这样回答面试官时更清楚：队列解决层次，双端队列解决方向。

四、也可以用数组下标填充

如果语言里双端队列不方便，可以先创建长度为 size 的数组。当前层从左到右时写入位置 i，从右到左时写入位置 size - 1 - i。这和头插尾插等价，但避免了链式结构的额外包装。

size=4, values=[1,2,3,4]
左到右下标: 0,1,2,3 -> [1,2,3,4]
右到左下标: 3,2,1,0 -> [4,3,2,1]

这种写法在 Java 中可以用 Integer[] level = new Integer[size]，最后转成 List。它的空间也是每层 O(size)。

五、复杂度和边界

每个节点只出队一次，左右孩子最多入队一次，所以时间复杂度 O(n)。队列最多保存一层节点，双端队列也最多保存一层节点，空间复杂度可写为 O(w)，其中 w 是树的最大宽度，最坏 O(n)。空树直接返回空列表。

满二叉树第 3 层宽度 = 8
此时队列最大规模约等于最大宽度

不要把空间简单说成 O(log n)。递归深度才和高度有关，层序队列和树的宽度有关，满二叉树最后一层可能接近 n/2。

六、常见误区与追问

心法：BFS 负责“按层”，方向变量只负责“本层怎么摆放”，两件事分开就不乱。

误区：奇数层要反向入队孩子。 改入队顺序会影响后续层的结构顺序，推荐只改变本层输出。
误区：不固定 size 也能按层输出。 不固定当前层大小会把下一层节点提前处理，层边界丢失。
误区：每层先正常收集再 reverse 一定最好。 reverse 也可以，但双端队列头插能少一次显式反转。
追问：空间复杂度为什么是 O(w)？ BFS 队列和层结果都与最大宽度有关，不是与高度直接相关。
追问：能用 DFS 做吗？ 可以，按深度收集列表，奇偶深度决定插入头尾，但 BFS 更贴合层序题意。
追问：如果输出节点对象而不是值呢？ 收集容器的元素类型换成节点即可，遍历框架不变。

七、加强记忆

锯齿形层序遍历只是在普通层序遍历上加了“摆盘方向”。队列还是一层一层推进，size 还是层边界，左右孩子还是稳定入队；唯一变化是本层结果从头插还是尾插。记住“队列定层，双端定向”，这题和普通层序遍历就不会混。

简化版

详细版