---
title: "199. Binary Tree Right Side View"
url: "https://laigary.com/interview/coding/199-binary-tree-right-side-view"
type: "note"
section: "coding"
date: "2024-03-12"
updated: "2026-07-28"
tags: ["Tree", "Breadth-First Search", "Depth-First Search"]
---

# 199. Binary Tree Right Side View

[199\. Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/)

站在樹的右邊往左看，由上到下能看到哪些節點。

## 思路

**這題就是 [102. 層序遍歷](/interview/coding/102-binary-tree-level-order-traversal) 換一行。** 站在右邊看，每一層只看得到**最右邊那一個**節點（它把同層左邊的都擋住了），所以骨架照抄，只把「收集整層」改成「只收最後一個」。

分層的關鍵一樣是先固定 `len(queue)`，那個數字就是這一層有幾個節點 —— 完整說明見 102。

### 「最右邊」不等於「一路往右走」

這是這題唯一的陷阱，而且很容易踩。直覺會想「從 root 一直往 `right` 走不就好了」，但右子樹可能比左子樹淺：

```text
        1
       / \
      2   3
     /
    4

右視圖：[1, 3, 4]
一路往右走：[1, 3]        ← 漏掉 4
```

第三層只有節點 4，而它是節點 2 的**左**子節點。所以「每層的最右節點」必須靠分層去找，不能靠往右走的路徑。

## 解題方向

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        
        if not root:
            return []

        queue = deque([root])
        res = []

        while queue:
            n = len(queue) - 1

            for i in range(len(queue)):
                node = queue.popleft()
                if i == n:
                    res.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                
        
        return res
```

`n = len(queue) - 1` 先記下這一層最後一個節點的位置，`i == n` 時才收集。**兩個 `len(queue)` 都在迴圈開始前就算完了**，所以即使迴圈裡不斷 `append` 下一層的節點，也不會影響這一輪的判斷。

**入列順序決定了誰是最後一個。** 因為是先 `append` 左再 `append` 右，佇列裡同層節點的順序就是由左到右，所以最後彈出的那個就是最右邊的。如果把左右順序對調，就要改成取第一個（`i == 0`），那等於是左視圖。

## 補充

**空樹要回傳 `[]` 不是 `None`。** 原本寫的是 `return root`，`root` 這時候是 `None`，跟型別標註 `List[int]` 對不上（[515](/interview/coding/515-find-largest-value-in-each-tree-row) 那題就寫對了）。已經改成 `return []`。

**也可以用 DFS 做**：走訪順序改成「根 → 右 → 左」，然後用 `len(res) == depth` 判斷是不是第一次到達這一層 —— 因為右邊先走，第一個到達某層的一定是最右節點。我沒有用這個角度寫過，但它跟 102 那篇的 DFS 版是同一個手法。

**同一個骨架的家族**：

| 題目 | 在那一層裡做什麼 |
|---|---|
| [102. Level Order](/interview/coding/102-binary-tree-level-order-traversal) | 收集整層 |
| 199 | **只取最後一個** |
| [515. Largest Value in Each Row](/interview/coding/515-find-largest-value-in-each-tree-row) | 取 max |
| [1302. Deepest Leaves Sum](/interview/coding/1302-deepest-leaves-sum) | 求和，只留最後一層 |
| [103. Zigzag Level Order](/interview/coding/103-binary-tree-zigzag-level-order-traversal) | 奇數層反轉 |
| [116](/interview/coding/116-populating-next-right-pointers-in-each-node) / [117](/interview/coding/117-populating-next-right-pointers-in-each-node-ii) | 把同層節點用 `next` 串起來 |

整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

## 複雜度

- 時間 $O(n)$ — 每個節點進出佇列各一次
- 空間 $O(w)$ — `w` 是最寬那層的節點數，完全二元樹的最後一層約 $n/2$，所以最壞是 $O(n)$

其中 $n$ 是節點數，輸出的 `res` 不計。