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

约 6 分钟
文章信息 24 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 200-500 面试经典 150 题 腾讯 字节 阿里 华为 微软 亚马逊 美团 京东 小米 百度 网易 小红书 快手 滴滴 B站 猿辅导 图森
标签
树 广度优先搜索 二叉树

题目描述

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

image-20260928184211145

image-20260928184211146

题意分析

按从上到下的层次返回二叉树节点值，第一层从左到右，第二层从右到左，之后逐层交替方向。每一层单独组成一个列表，空树返回空结果。

交替的是同一层中节点值的输出顺序，不是层的先后顺序，也不需要修改树的左右孩子。先正确地区分各层，再决定这一层的结果往哪个方向填写，就能把分层与方向两个问题分开处理。

解法：BFS 按层填充

核心思路

[!blue]

使用广度优先遍历，让每层节点始终按照树中从左到右的顺序被访问。队列最初只有根节点；处理每个节点时，依次收集它的左孩子和右孩子。由于父节点已经从左到右排列，按这个顺序收集的下一层也自然保持从左到右。

每层开始时记录当前节点数 size。Java 的队列会一边移出当前层节点、一边加入下一层节点，因此内层循环必须只处理固定的 size 次；Go 则把下一层单独放入 next，整层结束后再用它替换 queue。两种写法都保证一轮只处理一层。

用 leftToRight 表示本层结果的方向，创建长度为 size 的数组 level。访问本层第 i 个节点时，正向写入下标 i，反向写入 size - 1 - i。后一个下标把从左到右的访问顺序映射为从右到左的结果位置，恰好填满每个位置一次，不会遗漏或覆盖其他节点。

孩子的收集顺序始终不变，方向变化只影响 level 的写入位置。完成整层后保存结果，再翻转 leftToRight；直到没有下一层为止。这样不需要反转队列，也不会把本层的反向输出错误地传递到下一层的遍历顺序中。

解题步骤

  1. 空树直接返回空结果；否则将根节点放入队列，并令 leftToRight = true。
  2. 每层开始时记录 size，创建同样长度的 level。
  3. 按从左到右的结构顺序处理本层节点，正向写入 level[i]，反向写入 level[size - 1 - i]。
  4. 每个节点的非空孩子都按先左后右的顺序收集，留给下一轮处理。
  5. 保存本层结果并切换方向，继续处理下一层，直到队列为空。

代码实现

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();

        queue.offer(root);
        boolean leftToRight = true;

        while (!queue.isEmpty()) {
            int size = queue.size();
            Integer[] level = new Integer[size];

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                // 只改变当前层的写入位置，孩子入队顺序保持不变。
                int index = leftToRight ? i : size - 1 - i;

                level[index] = node.val;

                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            result.add(Arrays.asList(level));
            // 整层结束才切换方向。
            leftToRight = !leftToRight;
        }

        return result;
    }
}

func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }

    result := make([][]int, 0)
    queue := []*TreeNode{
        root,
    }
    leftToRight := true

    for len(queue) > 0 {
        size := len(queue)
        level := make([]int, size)
        next := make([]*TreeNode, 0, size*2)

        for i, node := range queue {
            index := i
            if !leftToRight {
                // 只改变当前层的写入位置，孩子收集顺序保持不变。
                index = size - 1 - i
            }
            level[index] = node.Val

            if node.Left != nil {
                next = append(next, node.Left)
            }
            if node.Right != nil {
                next = append(next, node.Right)
            }
        }

        result = append(result, level)
        queue = next
        // 整层结束才切换方向。
        leftToRight = !leftToRight
    }
    return result
}

复杂度分析

  • 时间复杂度：$O(n)$，每个节点只被访问并写入结果一次。
  • 空间复杂度：辅助空间为 $O(w)$，w 为二叉树的最大层宽，用于当前层、下一层与本层临时数组；返回结果另外占用 $O(n)$ 空间。

关键点总结

[!green]

  • 每层开始时必须固定 size，否则会把新入队的下一层节点提前处理。
  • 锯齿顺序通过写入下标实现，孩子仍按先左后右的结构顺序入队。
  • 遍历完一整层后再切换方向。

易错点总结

[!yellow]

  • 反向下标应为 size - 1 - i，少减 1 会越界。
  • 改变孩子入队顺序会破坏下一层原本的左右关系。
  • 空树未提前返回时，Java 的 ArrayDeque 不能接收空节点。
  • 在内层循环中切换方向，会变成按节点交替而不是按层交替。

相似题目

题目 难度 关联与区别
102. 二叉树的层序遍历 中等 BFS分层不变，本题只改变每层的写入方向，不必改变孩子的入队顺序。
199. 二叉树的右视图 中等 同样按层观察节点位置，原题每层只保留最右者，本题输出整层。
107. 二叉树的层序遍历 II 中等 按层遍历并在同一层内聚合；本题交替调整每层输出方向，该题把自顶向下的层结果反转。
515. 在每个树行中找最大值 中等 按层遍历并在同一层内聚合；本题交替调整每层输出方向，该题每层只保留最大节点值。
637. 二叉树的层平均值 简单 按层遍历并在同一层内聚合；本题交替调整每层输出方向，该题累计每层总和及节点数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/76709919
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！