📘 題目敘述
給你一棵二元樹的根節點 root。
想像你站在樹的右側，請依照從上到下的順序，回傳你能看見的節點值。
條件限制
- 樹中節點的數量在範圍
[0, 100] -100 <= Node.val <= 100
🧠 解題思路（一）BFS
題目提示叫我用 BFS 一層一層掃過去，因為「右側看到的節點」其實就是每一層最右邊那個節點。
因此我在 BFS 時做一件很固定的事情：先記錄當前層節點數量，完整處理這一層，並在這一層最後一個節點時收答案。
所有變數
ans：最後要回傳的右側視角節點值（由上到下）q：BFS 用的 queue，存下一個要處理的節點n：目前這一層的節點數量，用來確保只處理同一層節點node：目前從 queue 取出來正在處理的節點
🪜 主要流程步驟
1. 特例：空樹直接回傳空陣列
如果 root 是空的，代表沒有任何節點可以看到，直接回傳 ans。
2. 用 queue 做 BFS，確保一次處理一整層
先把 root 放進 q，每輪 while 開頭用 n = q.size() 記錄這層節點數，避免把下一層混進來。
3. 掃過這一層所有節點，同時把下一層推進 queue
每次取出 node 後，把存在的左右子節點推入 queue，做完 n 次就完成當前層。
4. 這一層最後處理到的節點就是右側看到的節點
在 for (i = 0 .. n-1) 裡，當 i == n - 1 時，把 node->val 放進 ans。
5. BFS 結束後回傳 ans
所有層都處理完，ans 就是從上到下的右側視角結果。
⏱️ 複雜度
- 時間複雜度：
O(n)，每個節點都只會進出 queue 一次。 - 空間複雜度：
O(n)，最壞情況 queue 可能同時存一整層節點。
💻 程式碼實作（一）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> ans;
if (!root) {
return ans;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int n = q.size();
for (int i = 0; i < n; i++) {
TreeNode* node = q.front();
q.pop();
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
if (i == n - 1) {
ans.push_back(node->val);
}
}
}
return ans;
}
};
🧠 解題思路（二）DFS
DFS 的核心想法是：右側看到的節點，就是每一層最先被看到的節點。
所以我固定用「先右再左」的順序走 DFS。每次第一次到達某層時，就把當前節點加入答案。
所有變數
h：目前已經記錄到的最大深度（代表ans已有幾層答案）ans：右側視角的節點值（由上到下）depth：目前 DFS 走到的深度（根節點從1開始）
🪜 主要流程步驟（二）DFS
1. 用 DFS 並且固定「先右再左」的走訪順序
遞迴函式 check(root, depth) 先走右子樹再走左子樹，確保同層右側節點先被拜訪。
2. 用 depth > h 判斷「這一層是不是第一次看到」
若條件成立，表示這層尚未收錄答案，當前節點就是右側視角，將它 push 進 ans 並更新 h。
3. 繼續往下遞迴，維持右優先
依序呼叫 check(root->right, depth + 1) 與 check(root->left, depth + 1)。
4. 從根開始呼叫 check，最後回傳 ans
在 rightSideView 中執行 check(root, 1)，DFS 完成後回傳 ans。
⏱️ 複雜度
- 時間複雜度：
O(n)，每個節點最多被拜訪一次。 - 空間複雜度：
O(h)，主要是遞迴堆疊深度；最壞鏈狀樹時為O(n)。
💻 程式碼實作（二）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
int h = 0;
vector<int> ans;
void check(TreeNode* root, int depth) {
if (root) {
if (depth > h) {
h++;
ans.push_back(root->val);
}
check(root->right, depth + 1);
check(root->left, depth + 1);
} else {
return;
}
}
vector<int> rightSideView(TreeNode* root) {
check(root, 1);
return ans;
}
};
🔗 題目連結
https://leetcode.com/problems/binary-tree-right-side-view/