製造焦慮：打破幻覺
這次是在微軟的一輪 Coding 面試中，候選人遇到的是一道典型的二元樹題。
很多人一看到「二元樹右視圖」就覺得簡單：「不就是 BFS 嗎？每層取最後一個節點就行了！」
沒那麼簡單。
這道題的考察點集中在層序遍歷的理解是否扎實，以及候選人能否在實現時把「層」的邊界說清楚。微軟在這一輪看的並不是「你會不會 BFS」，而是你能不能把一整套解題邏輯完整、穩定、無歧義地輸出出來。
題目拆解：展示專業
🔍 題目英文原文
面試官給出的題意比較簡潔，核心描述如下：
You are given the root of a binary tree.
Imagine yourself standing on the right side of the tree.
Return the values of the nodes you can see ordered from top to bottom.
If the tree is empty, return an empty array.
面試官在給完題目後，並沒有補充任何提示，直接讓候選人開始講理解。
📝 中文翻譯
給定一棵二元樹的根節點 root。
想像你站在樹的右側。
返回從上到下你能看到的節點值。
如果樹為空，返回空陣列。
🎯 範例分析
範例 1：
輸入:
1
/ \
2 3
\ \
5 4
輸出: [1, 3, 4]
解釋:
- 第 1 層: 只有 1，右視圖看到 1
- 第 2 層: 2 和 3，右視圖看到 3（最右邊）
- 第 3 層: 5 和 4，右視圖看到 4（最右邊）
範例 2：
輸入:
1
/
2
輸出: [1, 2]
解釋:
- 第 1 層: 只有 1
- 第 2 層: 只有 2（雖然在左邊，但這一層只有它，所以看得到）
範例 3：
輸入: null
輸出: []
題意澄清階段（Clarification）
候選人第一步沒有急著講演算法，而是先做了兩個確認，這一步非常關鍵：
- 「所以每一層只需要輸出一個值，對吧？就是這一層最右邊的那個節點。」
- 「如果輸入的 root 是 null，直接返回空陣列就可以，對嗎？」
面試官確認這兩個理解都是正確的。
這一步其實很關鍵，因為它直接把問題限定成了：按層處理 + 每層只取一個節點，後面所有實現都圍繞這個定義展開。
深度複盤：建立信任
🧠 題目本質分析
這道題考察的核心能力：
| 考點 | 具體內容 |
|---|---|
| BFS 層序遍歷 | 使用佇列逐層處理節點 |
| 層邊界判斷 | 記錄當前層節點數，處理完再進入下一層 |
| 右視圖定義 | 每層最後一個被處理的節點 |
| 邊界處理 | 空樹、單節點、左偏樹、右偏樹 |
📊 關鍵洞察
為什麼是 BFS 而不是 DFS？
- BFS 天然按「層」處理，每層結束時能明確知道哪個是最後一個節點
- DFS 需要額外維護深度資訊，且需要「先右後左」遍歷才能保證右視圖正確
層邊界是關鍵
- 在 BFS 中，進入 while 迴圈時，佇列裡恰好是當前層的所有節點
- 記錄
levelSize = queue.size()，然後 for 迴圈處理這麼多個節點 - 當
i == levelSize - 1時，就是這一層的最後一個節點（右視圖節點）
方案引入：核心演算法
解法：BFS 層序遍歷
from collections import deque
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rightSideView(root: Optional[TreeNode]) -> List[int]:
"""
Microsoft VO 真題：二元樹右視圖
Args:
root: 二元樹根節點
Returns:
List[int]: 從右側看到的節點值列表
"""
# Step 1: 邊界處理 - 空樹直接返回空陣列
if not root:
return []
result = []
queue = deque([root])
# Step 2: BFS 層序遍歷
while queue:
# 記錄當前層的節點數量（關鍵！）
level_size = len(queue)
# Step 3: 處理當前層的所有節點
for i in range(level_size):
node = queue.popleft()
# Step 4: 當處理到這一層的最後一個節點時，記錄其值
if i == level_size - 1:
result.append(node.val)
# Step 5: 將左右子節點加入佇列（先左後右）
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
Java 實現（面試常用）
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
// Step 1: 邊界處理
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// Step 2: BFS 層序遍歷
while (!queue.isEmpty()) {
// 記錄當前層的節點數量
int levelSize = queue.size();
// Step 3: 處理當前層的所有節點
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
// Step 4: 最後一個節點是右視圖節點
if (i == levelSize - 1) {
result.add(node.val);
}
// Step 5: 左右子節點入隊
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return result;
}
}
🧪 測試用例
# 構建測試樹的輔助函數
def build_tree(values):
"""從層序陣列構建二元樹"""
if not values or values[0] is None:
return None
root = TreeNode(values[0])
queue = deque([root])
i = 1
while queue and i < len(values):
node = queue.popleft()
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
# Test 1: 標準範例
root1 = build_tree([1, 2, 3, None, 5, None, 4])
print(rightSideView(root1)) # Expected: [1, 3, 4]
# Test 2: 左偏樹
root2 = build_tree([1, 2, None])
print(rightSideView(root2)) # Expected: [1, 2]
# Test 3: 空樹
root3 = None
print(rightSideView(root3)) # Expected: []
# Test 4: 單節點
root4 = TreeNode(1)
print(rightSideView(root4)) # Expected: [1]
# Test 5: 完全二元樹
root5 = build_tree([1, 2, 3, 4, 5, 6, 7])
print(rightSideView(root5)) # Expected: [1, 3, 7]
# Test 6: 右偏樹
root6 = build_tree([1, None, 2, None, 3])
print(rightSideView(root6)) # Expected: [1, 2, 3]
# Test 7: 深度不一致
root7 = build_tree([1, 2, 3, 4])
print(rightSideView(root7)) # Expected: [1, 3, 4]
解法二：DFS（先右後左）
def rightSideView_dfs(root: Optional[TreeNode]) -> List[int]:
"""
DFS 解法：先右後左遍歷，每層第一個訪問的就是右視圖節點
"""
result = []
def dfs(node: TreeNode, depth: int):
if not node:
return
# 如果當前深度首次訪問，記錄該節點
if depth == len(result):
result.append(node.val)
# 先右後左遍歷（保證每層先訪問最右邊的節點）
dfs(node.right, depth + 1)
dfs(node.left, depth + 1)
dfs(root, 0)
return result
複雜度分析
| 方法 | 時間複雜度 | 空間複雜度 |
|---|---|---|
| BFS 層序遍歷 | O(n) | O(n) 最壞情況佇列存儲一層所有節點 |
| DFS 先右後左 | O(n) | O(h) 遞迴堆疊深度，h 為樹高 |
其中 n = 節點總數，h = 樹的高度
🤯 面試官的 Followup 陷阱
Followup 1: 如果要求左視圖呢？
答案：取每層第一個節點而不是最後一個。
def leftSideView(root):
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 == 0: # 第一個節點是左視圖節點
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
Followup 2: 如何返回每層的所有節點值？
答案：這就是經典的「層序遍歷」（LeetCode 102）。
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
Followup 3: 如何返回底視圖（Bottom View）？
答案：需要記錄每個節點的水平距離，取每個水平距離上最底部的節點。
Followup 4: 如何返回垂直視圖（Vertical Order）？
答案：按水平距離分組，同一水平距離按深度排序。
🔥 為什麼大多數人會掛？
| 常見錯誤 | 正確做法 |
|---|---|
沒有記錄 levelSize |
進入 while 迴圈時先記錄當前層節點數 |
用 queue.size() 在 for 迴圈判斷 |
佇列大小會變，必須提前固定 |
| 左右子節點入隊順序錯誤 | 先左後右（BFS）或先右後左（DFS） |
| 空樹沒處理 | 第一行就判空返回 [] |
| Clarification 階段沒確認 | 先確認「每層一個值」「null 返回空陣列」 |
面試官真正看的是什麼？
這道題本身不難，微軟在這一輪看的並不是「你會不會 BFS」，而是：
- Clarification 能力：你能否主動澄清題意，把模糊需求變成明確定義
- 表述完整性：你能否把一整套解題邏輯完整、穩定、無歧義地輸出
- 程式碼實現穩定性：你能否在壓力下寫出 bug-free 的程式碼
- 複雜度分析：你能否準確給出時間和空間複雜度
程式碼模板（可直接使用）
from collections import deque
def rightSideView(root):
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
📞 oavoservice 服務
在這道題裡，oavoservice 提供的是可直接照抄的完整解題文本和實現結構，候選人只需要按節奏輸出，就能穩穩走完整題。
如果你也在準備微軟或者其他科技大廠的面試，我們提供：
- ✅ VO輔助：即時場外助攻，幫你解決面試中的任何問題
- ✅ 代面試：專業工程師全程代替
- ✅ OA代寫：CodeSignal / HackerRank 滿分保障
- ✅ 面試輔助：完整解題文本 + 實現結構，按節奏穩穩輸出
👉 立即添加微信：Coding0201
不要讓一道二元樹題，毀掉你的 Microsoft Offer。
本文由 oavoservice 團隊原創，轉載請註明出處。