Binary Tree Right Side View
題目描述
給定一棵二元樹的根節點 root，回傳從右側看到的節點值（從上到下排列）。
輸入: 1
/ \
2 3
\ \
5 4
輸出: [1, 3, 4]
輸入: 1
\
3
輸出: [1, 3]
解題思路
初始化 Queue
將 root 放入 Queue，準備開始逐層遍歷
逐層遍歷
用 levelSize = queue.Count 記錄當前層節點數，內層迴圈只處理這麼多個
記錄每層最後一個
當 i == levelSize - 1 時，該節點是這一層最右邊的，加入結果列表
加入子節點
對每個出隊節點，先加左子再加右子到 Queue，作為下一層的來源
程式碼
C#
public class Solution {
public IList<int> RightSideView(TreeNode root) {
var result = new List<int>();
if (root == null) return result;
var queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0) {
int levelSize = queue.Count;
for (int i = 0; i < levelSize; i++) {
var node = queue.Dequeue();
// 每層最後一個節點
if (i == levelSize - 1) result.Add(node.val);
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
}
return result;
}
}TypeScript
function rightSideView(root: TreeNode | null): number[] {
if (!root) return [];
const result: number[] = [];
const queue: TreeNode[] = [root];
while (queue.length > 0) {
const levelSize = queue.length;
for (let i = 0; i < levelSize; i++) {
const node = queue.shift()!;
if (i === levelSize - 1) result.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
return result;
}Python
from collections import deque
def rightSideView(root: Optional[TreeNode]) -> list[int]:
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
if i == level_size - 1: # 每層最後一個
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(w) |
w 是樹的最大寬度，最壞 O(n)。Time O(n) 是因為每個節點恰好入隊出隊一次。Space O(w) 是因為 Queue 同時最多存放一層的所有節點，完全二元樹最底層有 n/2 個節點。
邊界情況
- 空樹：root 為 null，直接回傳空列表
- 只有左子樹的鏈：如
1→2→3全往左，每層只有一個節點，右側看到的就是每層唯一的節點 - 完全二元樹：每層最右邊的節點就是從右邊看到的，結果列表長度等於樹高
圖解
圖表展示了三層 BFS 的過程：第 0 層只有 1（可見）、第 1 層有 2 和 3 取最後一個 3（可見）、第 2 層有 5 和 4 取最後一個 4（可見），結果 [1, 3, 4]。
進階觀點
💡面試追問
Q: 如何用 DFS 解？
A: 用 DFS 先走右子樹再走左子樹，維護 depth 變數。當 depth == result.length 代表這是該層第一次被訪問的節點（因為先走右，所以是最右邊的）。Space 為 O(h) 優於 BFS 的 O(w)。
Q: 如何改成 Left Side View？
A: BFS 方案中把條件改為 i == 0（每層第一個元素）。DFS 方案中改為先走左子樹再走右子樹。
變體題：LC 116 Populating Next Right Pointers、LC 102 Binary Tree Level Order Traversal。
理解測驗
🤔 為什麼用 BFS 而不是 DFS 來解這題更直覺？
🤔 如果某層只有左子節點沒有右子節點，右側看到的是哪個？