給定一棵二元樹，回傳其節點值的層序遍歷結果。即逐層從左到右收集每層的節點值。
Example:
Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]
Intuition
TIP
BFS 逐層處理：每次取出佇列中當前層的所有節點，收集值後將下一層節點加入佇列。
- BFS 天然適合層序遍歷，關鍵是用
queue.size來界定每一層 - DFS 也可以做，透過傳遞 depth 參數將節點值放入對應層的列表
Approaches
⭐ 1. BFS (queue) — O(n) / O(n)
- Idea: 使用佇列逐層遍歷，每層開始時記錄當前佇列大小
- Time:
O(n) - Space:
O(n)
class Solution {
fun levelOrder(root: TreeNode?): List<List<Int>> {
val result = mutableListOf<List<Int>>()
if (root == null) return result
val queue: ArrayDeque<TreeNode> = ArrayDeque()
queue.add(root)
while (queue.isNotEmpty()) {
val level = mutableListOf<Int>()
val size = queue.size
for (i in 0 until size) {
val node = queue.removeFirst()
level.add(node.`val`)
node.left?.let { queue.add(it) }
node.right?.let { queue.add(it) }
}
result.add(level)
}
return result
}
}2. DFS (Recursive) — O(n) / O(n)
- Idea: 前序遍歷，傳遞當前深度，將節點值加入對應層的列表
- Time:
O(n) - Space:
O(n)
class Solution {
fun levelOrder(root: TreeNode?): List<List<Int>> {
val result = mutableListOf<MutableList<Int>>()
dfs(root, 0, result)
return result
}
private fun dfs(node: TreeNode?, depth: Int, result: MutableList<MutableList<Int>>) {
if (node == null) return
if (depth == result.size) {
result.add(mutableListOf())
}
result[depth].add(node.`val`)
dfs(node.left, depth + 1, result)
dfs(node.right, depth + 1, result)
}
}🔑 Takeaways
- Pattern: BFS 層序遍歷模板 — 用
queue.size界定每層邊界 - Key trick: 這個 BFS 模板是很多變體題的基礎（右視圖、鋸齒形遍歷、每層最大值等）