199. Binary Tree Right Side View

Medium

Description

給定一棵二元樹，想像你站在樹的右側，回傳從上到下你能看到的每層最右邊的節點值。

Example:

Input: root = [1,2,3,null,5,null,4] Output: [1,3,4]

Intuition#

每一層的最後一個節點就是右側視圖能看到的節點。

BFS 逐層遍歷，取每層最後一個節點
DFS 可以用「先右後左」的方式，每層第一個被訪問的就是最右節點

Approaches#

⭐ 1: BFS#

概念: 層序遍歷，每層的最後一個節點加入結果
時間複雜度: O(n)
空間複雜度: O(n)

class Solution {
    fun rightSideView(root: TreeNode?): List<Int> {
        val result = mutableListOf<Int>()
        if (root == null) return result
        val queue: ArrayDeque<TreeNode> = ArrayDeque()
        queue.add(root)
        while (queue.isNotEmpty()) {
            val size = queue.size
            for (i in 0 until size) {
                val node = queue.removeFirst()
                if (i == size - 1) {
                    result.add(node.`val`)
                }
                node.left?.let { queue.add(it) }
                node.right?.let { queue.add(it) }
            }
        }
        return result
    }
}

2: DFS（右子樹優先）#

概念: 先遍歷右子樹，當 depth 等於 result 大小時代表該層尚未記錄，加入結果
時間複雜度: O(n)
空間複雜度: O(h)

class Solution {
    fun rightSideView(root: TreeNode?): List<Int> {
        val result = mutableListOf<Int>()
        dfs(root, 0, result)
        return result
    }

    private fun dfs(node: TreeNode?, depth: Int, result: MutableList<Int>) {
        if (node == null) return
        if (depth == result.size) {
            result.add(node.`val`)
        }
        dfs(node.right, depth + 1, result)
        dfs(node.left, depth + 1, result)
    }
}

🔑 Takeaways#

Pattern: BFS 層序遍歷的變體 — 只取每層特定位置的節點
關鍵技巧: DFS 中 depth == result.size 是判斷「該層是否已記錄」的巧妙方法