102. Binary Tree Level Order Traversal

Medium

Description

給定一棵二元樹，回傳其節點值的層序遍歷結果。即逐層從左到右收集每層的節點值。

Example:

Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]

Intuition#

BFS 逐層處理：每次取出佇列中當前層的所有節點，收集值後將下一層節點加入佇列。

BFS 天然適合層序遍歷，關鍵是用 queue.size 來界定每一層
DFS 也可以做，透過傳遞 depth 參數將節點值放入對應層的列表

Approaches#

⭐ 1: BFS（佇列）#

概念: 使用佇列逐層遍歷，每層開始時記錄當前佇列大小
時間複雜度: O(n)
空間複雜度: 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（遞迴）#

概念: 前序遍歷，傳遞當前深度，將節點值加入對應層的列表
時間複雜度: O(n)
空間複雜度: 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 界定每層邊界
關鍵技巧: 這個 BFS 模板是很多變體題的基礎（右視圖、鋸齒形遍歷、每層最大值等）