85.二叉树的锯齿形层序遍历
题目
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
- 输入：root = [3,9,20,null,null,15,7]
- 输出：[[3],[20,9],[15,7]]
示例 2：
- 输入：root = [1]
- 输出：[[1]]
示例 3：
- 输入：root = []
- 输出：[]
提示：
- 树中节点数目在范围 [0, 2000] 内
- -100 <= Node.val <= 100
思路
规则很简单：层号（从 0 开始）是偶数就正序，奇数就倒序。
二、先掐死一个大坑：不要去改入队顺序
绝大多数人第一反应是："既然这层要倒序，那我就把孩子改成先右后左入队。"
这个想法是错的，而且错得很隐蔽——它在只有两三层的树上能过，层数一多就崩。
看这棵满二叉树，正确答案是 [[1], [3,2], [4,5,6,7]]：
1
/ \
2 3
/ \ / \
4 5 6 7
按"交替入队顺序"的思路走：
- 第 0 层处理 1，为了让第 1 层倒序，改成先右后左入队 → 队列 [3, 2]
- 第 1 层出队得到 [3, 2] ✅ 看起来成功了
- 第 2 层希望得到 [4,5,6,7]。但队列里 3 排在 2 前面，先处理 3，它的孩子 6,7 先进队；再处理 2，孩子 4,5 后进队 → 队列变成 [6,7,4,5]（或倒序 [7,6,5,4]）
无论你怎么调这一层的入队顺序，4,5 都被甩到了 6,7 后面，再也拼不出 [4,5,6,7]。
根本原因： 一旦你把队列的物理顺序搞乱，这个混乱会累积传递到后面所有层。上一层的乱序决定了下一层孩子的入队先后，这是你无法在本 层内修正的。
正确心法：
▎ 队列永远保持"先左后右"入队，物理顺序始终是标准的左→右。只在"往结果里写"的那一刻决定正序还是倒序。
也就是说——遍历逻辑不动，只动输出。
class Solution {
fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> {
val result = mutableListOf<MutableList<Int>>()
if (root == null) {
return result
}
val queue = ArrayDeque<TreeNode?>()
queue.addLast(root)
// 标记当前层是否为"从左到右"，第 0 层是正序
var leftToRight = true
while (queue.isNotEmpty()) {
val size = queue.size
val list = mutableListOf<Int>()
for (i in 0 until size) {
val node = queue.removeFirst()
node?.let {
list.add(it.`val`)
if (it.left != null) {
queue.addLast(it.left)
}
if (it.right != null) {
queue.addLast(it.right)
}
}
}
// 只在"输出"这一刻决定方向：奇数层反转
if (!leftToRight) {
list.reverse()
}
result.add(list)
// 翻转标记，下一层换方向
leftToRight = !leftToRight
}
return result
}
}
关于 reverse() 会不会拖慢： 不会。每层反转的代价是该层节点数，所有层加起来恰好是 n，所以总复杂度仍是 O(n)。
复杂度
- 时间复杂度: O(n)
- 空间复杂度: O(w)
- 邮箱 ：charon.chui@gmail.com
- Good Luck!