制造焦虑：打破幻觉
这次是在微软的一轮 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 团队原创，转载请注明出处。