問題描述

給定二叉樹，站在右側看，返回每層最右側節點值組成的列表。例如：

    1
   / \
  2   3
   \   \
    5   4
輸出：[1,3,4]

BFS 層序遍歷解法

標準層序遍歷，每層記錄最後一個節點（最右）。為了讓最右節點先出隊，入隊順序：先右後左。

代碼實現

class Solution {
public:
    vector rightSideView(TreeNode* root) {
        vector res;
        if (!root) return res;
        queue q;
        q.push(root);
        while (!q.empty()) {
            int sz = q.size();
            for (int i=0; ival); // 每層第一個（最右）
                if (node->right) q.push(node->right);
                if (node->left) q.push(node->left);
            }
        }
        return res;
    }
};

關鍵點

1. 入隊順序：先右後左，使每層最右節點排在隊列最前，i==0 即為目標。
2. 層大小：sz = q.size() 在循環開始前捕獲，避免新入隊節點干擾。
3. 空樹處理：if(!root) return {}。

替代方案：DFS 先序遍歷（根-右-左）

void dfs(TreeNode* node, int depth, vector& res) {
    if (!node) return;
    if (depth == res.size()) res.push_back(node->val); // 首次到達該深度
    dfs(node->right, depth+1, res);
    dfs(node->left, depth+1, res);
}
vector rightSideView(TreeNode* root) {
    vector res;
    dfs(root, 0, res);
    return res;
}

DFS 先訪問右子樹，保證每深度第一個訪問到的節點即最右節點。代碼更簡潔，空間複雜度 O(H)（遞歸棧）。

總結

LeetCode 199 考察二叉樹層序/DFS 遍歷變體。BFS 先右後左 + 取每層首個，或 DFS 根右左 + 記錄首次到達深度，均為標準解法。BFS 直觀易懂，DFS 代碼極短。面試中兩種均可，關鍵是能說清「為什麼先右後左」或「為什麼 DFS 先訪問右子樹」。