题目重点：按层固定队列长度遍历，交替从层结果尾/头插入，并讨论双栈替代方案。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版返回每层节点值数组，第一层从左到右、第二层从右到左，之后交替。
- 空树返回空数组；节点值允许重复，遍历顺序按树结构不是值排序。
- 不修改树；队列中一直按真实左儿子、右儿子顺序加入。
解题路线
- 标准 BFS 把 root 入队，每轮先读当前队列长度，恰好弹出这一层，避免下一层节点混入。
- 方向为左到右时把值 append 到本层 deque，右到左时 appendleft；子节点始终左后右入队。
- 本层完成转成数组、翻转方向；因此第 d 层值顺序正是该层水平顺序或其反序。
- 也可两栈交替：当前层弹出时按下一层期望方向控制子节点入栈顺序，避免每层结果翻转；但状态和入栈方向更易写错。
手动走一遍
根 1，下一层 2/3，再下一层 4/5/6/7，输出 [[1],[3,2],[4,5,6,7]]。如果只把队列入队方向反过来，下一层结构顺序容易错；把显示顺序与遍历顺序分开更清楚。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Zigzag breadth-first traversal of a binary tree."""
from collections import deque
from dataclasses import dataclass
@dataclass(eq=False)
class TreeNode:
value: int
left: "TreeNode | None" = None
right: "TreeNode | None" = None
def zigzag_level_order(root: TreeNode | None) -> list[list[int]]:
if root is None:
return []
queue = deque([root])
result = []
left_to_right = True
while queue:
level = deque()
for _ in range(len(queue)):
node = queue.popleft()
if left_to_right:
level.append(node.value)
else:
level.appendleft(node.value)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
result.append(list(level))
left_to_right = not left_to_right
return result
复杂度
n 个节点每个入队/出队一次，时间 O(n)；队列、本层缓冲及结果占 O(n) 总空间，忽略返回结果时辅助空间受最宽层 O(w) 约束。
易错点与追问
容易失分的边界
- 不在每轮固定队列长度，层边界混淆。
- 右到左层连儿子入队顺序也乱改，导致后续层不对。
- 误把锯齿形遍历当深度优先交替。
- 空树没做处理。
继续深挖
- 两个栈交替时每层子节点入栈顺序是什么？
- 只要求迭代输出而非保存全部层，内存如何降？
- N 叉树如何适配？
