199. Binary Tree Right Side View

──────────────────────────────────────────────────────────────────────

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

思路

這題就是 102. 層序遍歷換一行。 站在右邊看，每一層只看得到最右邊那一個節點（它把同層左邊的都擋住了），所以骨架照抄，只把「收集整層」改成「只收最後一個」。

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

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

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

        1
       / \
      2   3
     /
    4

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

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

解題方向

# 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 那題就寫對了）。已經改成 return []。

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

同一個骨架的家族：

題目	在那一層裡做什麼
102. Level Order	收集整層
199	只取最後一個
515. Largest Value in Each Row	取 max
1302. Deepest Leaves Sum	求和，只留最後一層
103. Zigzag Level Order	奇數層反轉
116 / 117	把同層節點用 `next` 串起來

整理見 Tree 遍歷模板。

複雜度

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

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