給定一棵二元樹的根節點，回傳其鋸齒形層序遍歷（Zigzag Level Order）。即先從左到右，下一層從右到左，交替進行。
Example:
Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]]
Intuition
TIP
標準 BFS 層序遍歷，偶數層正序、奇數層反序即可。
- 基本架構與普通的層序遍歷 (102) 相同
- 唯一差異是交替層需要反轉節點值的順序
- 可以用一個布林旗標控制方向
Approaches
⭐ 1. BFS with Direction Flag — O(n) / O(n)
- Idea: BFS 層序遍歷，用旗標控制每層是正序還是反序加入結果
- Time:
O(n)，每個節點訪問一次 - Space:
O(n)，佇列最多存放一層的節點
class Solution {
fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> {
val result = mutableListOf<List<Int>>()
if (root == null) return result
val queue = ArrayDeque<TreeNode>()
queue.add(root)
var leftToRight = true
while (queue.isNotEmpty()) {
val size = queue.size
val level = ArrayDeque<Int>()
repeat(size) {
val node = queue.removeFirst()
if (leftToRight) {
level.addLast(node.`val`)
} else {
level.addFirst(node.`val`)
}
node.left?.let { queue.add(it) }
node.right?.let { queue.add(it) }
}
result.add(level.toList())
leftToRight = !leftToRight
}
return result
}
}2. BFS + Reverse — O(n) / O(n)
- Idea: 正常 BFS 層序遍歷，奇數層直接反轉結果列表
- Time:
O(n) - Space:
O(n)
class Solution {
fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> {
val result = mutableListOf<List<Int>>()
if (root == null) return result
val queue = ArrayDeque<TreeNode>()
queue.add(root)
var level = 0
while (queue.isNotEmpty()) {
val size = queue.size
val levelList = mutableListOf<Int>()
repeat(size) {
val node = queue.removeFirst()
levelList.add(node.`val`)
node.left?.let { queue.add(it) }
node.right?.let { queue.add(it) }
}
if (level % 2 == 1) levelList.reverse()
result.add(levelList)
level++
}
return result
}
}🔑 Takeaways
- Pattern: BFS 層序遍歷的變形 — 加上方向控制
- Key trick: 使用
ArrayDeque的addFirst/addLast可以避免反轉操作，更優雅地控制插入方向