题目描述
思路解析动画文字版
思路一句话：BFS 一点没变，只用一个 flag 控制——偶数层把该层结果 reverse。下面一步步演给你看。
根节点入队。第 1 层方向＝左到右。
出队 3：先按出队顺序攒进第 1 层缓冲。
3 的孩子 9 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
3 的孩子 20 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。 第 1 层（左→右）收完：[3]——队列里现在全是下一层，方向翻转，继续。
出队 9：先按出队顺序攒进第 2 层缓冲。
9 的孩子 8 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
9 的孩子 10 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
出队 20：先按出队顺序攒进第 2 层缓冲。
20 的孩子 15 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
20 的孩子 7 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。 第 2 层（右→左）：把出队序列 [9, 20] 翻转 → [20, 9]——队列里现在全是下一层，方向翻转，继续。
出队 8：先按出队顺序攒进第 3 层缓冲。
8 的孩子 1 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
8 的孩子 2 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
出队 10：先按出队顺序攒进第 3 层缓冲。
10 的孩子 4 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
10 的孩子 6 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
出队 15：先按出队顺序攒进第 3 层缓冲。
15 的孩子 5 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
出队 7：先按出队顺序攒进第 3 层缓冲。 第 3 层（左→右）收完：[8, 10, 15, 7]——队列里现在全是下一层，方向翻转，继续。
出队 1：先按出队顺序攒进第 4 层缓冲。
出队 2：先按出队顺序攒进第 4 层缓冲。
出队 4：先按出队顺序攒进第 4 层缓冲。
出队 6：先按出队顺序攒进第 4 层缓冲。
出队 5：先按出队顺序攒进第 4 层缓冲。 第 4 层（右→左）：把出队序列 [1, 2, 4, 6, 5] 翻转 → [5, 6, 4, 2, 1]——队列里现在全是下一层，方向翻转，继续。
空树、单节点都和普通层序一样；从第二层起才看出“之字”。
面试里讲清“遍历不变、只翻收集方向”，再补一句双端队列免翻转的优化，就很完整了。
参考代码
def zigzagLevelOrder(root): if not root: return [] res, q, leftToRight = [], deque([root]), True while q: level = [] for _ in range(len(q)): # 锁定本层个数 node = q.popleft() # 出队一个 level.append(node.val) # 永远按出队(左→右)攒 if node.left: q.append(node.left) # 孩子照常左右入队 if node.right: q.append(node.right) res.append(level if leftToRight else level[::-1]) # 偶数层翻转 leftToRight = not leftToRight # 方向交替 return res复杂度
- 时间：O(n)，每个节点入队出队各一次；偶数层翻转总计也是 O(n)
- 空间：O(n)，队列最多装下最宽一层的节点
易错点
面试追问把动画讲成自己的话
追问锯齿层序和普通层序差在哪？
追问能不能不额外翻转、在遍历时就排好？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
从前序与中序遍历序列构造二叉树
LeetCode 105 · 中等 · 沿着 二叉树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题