LeetCode 199中等二叉树 · BFS
二叉树右视图 图解题解
从右边看一棵树，你究竟能看到哪些节点？
站在楼梯右侧往左看，每一级台阶只看到最靠近你的那个人，后面的被挡住了。BFS 把树一层层展开，每层末尾那个节点就是「站在右边最先看到的」；同层靠左的节点被更右的兄弟遮住，根本入不了右视图。
这道题到底在问什么
给一棵二叉树，假设你站在它的右侧，返回从上到下你能看到的节点值。每一层只看得到最右边那一个。
- 输入
- 上图这棵树
- 输出
- [1, 3, 7, 13]
最优解：一步一步想明白
- 3记住这条：BFS 每层从左往右出队，最后出队的那个就在最右边，收下它。
- 4根节点入队，开始逐层 BFS。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 5出队 1：它是第 1 层最后一个出队的——也就是这一层最右节点。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 6站右边看，第 1 层只看得到 1，记入右视图。右视图现在：[1]——继续下一层，依旧只取最右。
- 71 的孩子 2 入队，排到下一层。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 81 的孩子 3 入队，排到下一层。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 9出队 2：第 2 层的节点，但它右边还有同层节点，看不到。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 102 的孩子 4 入队，排到下一层。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 112 的孩子 5 入队，排到下一层。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 12出队 3：它是第 2 层最后一个出队的——也就是这一层最右节点。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 13站右边看，第 2 层只看得到 3，记入右视图。右视图现在：[1, 3]——继续下一层，依旧只取最右。
- 143 的孩子 6 入队，排到下一层。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 153 的孩子 7 入队，排到下一层。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 16出队 4：第 3 层的节点，但它右边还有同层节点，看不到。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 174 的孩子 8 入队，排到下一层。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 18出队 5：第 3 层的节点，但它右边还有同层节点，看不到。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 195 的孩子 11 入队，排到下一层。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 20出队 6：第 3 层的节点，但它右边还有同层节点，看不到。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 216 的孩子 13 入队，排到下一层。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 22出队 7：它是第 3 层最后一个出队的——也就是这一层最右节点。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 23站右边看，第 3 层只看得到 7，记入右视图。右视图现在：[1, 3, 7]——继续下一层，依旧只取最右。
- 24出队 8：第 4 层的节点，但它右边还有同层节点，看不到。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 25出队 11：第 4 层的节点，但它右边还有同层节点，看不到。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 26出队 13：它是第 4 层最后一个出队的——也就是这一层最右节点。每层最后一个出队的就是最右；BFS 是从左到右出队，所以最后那个一定在最右边。
- 27站右边看，第 4 层只看得到 13，记入右视图。右视图现在：[1, 3, 7, 13]——继续下一层，依旧只取最右。
⚠️ 容易写错的地方
✗ 错：以为右视图就是「一路走右孩子」
✓ 对：按层取最右的实际节点
某层右边缺节点时，最右是左子树伸下来的节点
✗ 错：不锁本层个数
✓ 对：进 for 前先存 sz=q.size()
循环里队列在变长，分不清谁是本层最后一个
✗ 错：左右孩子漏判 null
✓ 对：只把非空孩子入队
null 入队会污染层数和顺序
完整代码（Python / Java / C++）
Python
def rightSideView(root):
if not root: return []
res, q = [], deque([root])
while q:
sz = len(q) # 锁定本层个数
for i in range(sz):
node = q.popleft() # 从左到右出队
if i == sz - 1: # 本层最后一个 = 最右
res.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return resJava
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int sz = q.size(); // 锁定本层个数
for (int i = 0; i < sz; i++) {
TreeNode node = q.poll(); // 从左到右出队
if (i == sz - 1) // 本层最后一个 = 最右
res.add(node.val);
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
}
return res;
}C++
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if (!root) return res;
queue<TreeNode*> q; q.push(root);
while (!q.empty()) {
int sz = q.size(); // 锁定本层个数
for (int i = 0; i < sz; ++i) {
TreeNode* node = q.front(); q.pop(); // 从左到右出队
if (i == sz - 1) // 本层最后一个 = 最右
res.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return res;
}复杂度
时间
O(n)
每个节点恰好入队、出队各一次
空间
O(n)
队列最多装下最宽一层的节点
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二叉树右视图 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能用 DFS 做右视图？+
可以。按「根→右→左」的顺序 DFS，每个深度第一次到达的节点就是该层最右；用一个 res 数组，当 depth == len(res) 时记录。
右视图为什么不是一路走右孩子？+
因为某层的右半边可能为空，这时最右节点其实是左子树伸下来的。必须按「层」取实际存在的最右节点。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 二叉树右视图 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。