199. 二叉树的右视图 (Medium)
专题归类： 05-二叉树 LeetCode 链接： https://leetcode.cn/problems/binary-tree-right-side-view/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1：
输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]
示例 2：
输入：root = [1,null,3]
输出：[1,3]
示例 3：
输入：root = []
输出：[]
提示：
- 树的节点数范围
[0, 100] -100 <= Node.val <= 100
题目详细分析
- 数据范围含义： 最多 100 个节点，非常小。任何算法都可以。
- 输入输出特征： 输入根节点，输出一个列表，长度等于树的高度（每层贡献一个值）。
- 边界条件： 空树返回 []；只有右子树时右视图就是前序遍历本身；只有左子树时右视图就是每层最右边的节点（可能在左边）。
- 核心约束： 「右侧能看到」意味着每层只能看到最右边的那个节点。注意：最右边的节点不一定在右子树上——如果左子树比右子树深，左子树的下层节点可能成为右视图的一部分。
- 隐藏条件： 这本质上是「每层最右节点」问题。也可以理解为按「根→右→左」的顺序 DFS，每层第一个访问到的节点。
小白版直白理解
就像你站在一棵大树的右边往左边看——每层你只能看到最靠右的那个节点，因为左边的节点都被右边的挡住了。如果某一层右子树没有节点而左子树有，你看到的就是左子树最靠右的那个节点。简单说就是：每层取最右边的节点。
解题思路
思路一：BFS 层序遍历（推荐）
核心思想： 对二叉树做层序遍历，每层取最后一个节点放入结果集。
为什么 BFS 适合？ BFS 天然按层处理，在每层遍历时很容易知道当前节点是不是该层的最后一个（判断 i 是否等于 len(q)-1 或 level_size-1）。思路非常直观，不容易出错。
from collections import deque
def rightSideView(root):
if not root:
return []
res = []
q = deque([root])
while q:
level_size = len(q)
for i in range(level_size):
node = q.popleft()
# 如果是当前层的最后一个节点，加入结果
if i == level_size - 1:
res.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return res思路二：DFS 反向先序遍历（根→右→左）
核心思想： 按照「根节点 → 右子树 → 左子树」的顺序进行 DFS。每层第一个访问到的节点就是该层最右边的节点。
为什么用这种顺序？ 前序是「根→左→右」，而我们改成「根→右→左」。这样每层最先访问到的就是最右边的节点。用 depth == len(res) 判断是否是该层第一个被访问的节点——因为 DFS 优先走右边，所以每层第一个到达的节点就是右视图应该看到的。
def rightSideView(root):
res = []
def dfs(node, depth):
if not node:
return
# 当前层还没有记录节点 → 当前节点是该层第一个访问到的（也是最右边的）
if depth == len(res):
res.append(node.val)
# 先走右边（保证右边节点优先被访问）
dfs(node.right, depth + 1)
dfs(node.left, depth + 1)
dfs(root, 0)
return res易错点
- 右视图不只看右子树： 如果左子树比右子树深，底部的节点虽然在左子树但仍然能从右边看到（因为右子树没有挡住它）。所以不能只取右子树上的节点。
- BFS 中
len(q)必须固定：for i in range(len(q))中len(q)必须提前赋值给变量，否则会在循环中变化。 - DFS 法的条件
depth == len(res)： 只有首次到达某深度时才记录，后续再到达同一深度（从左子树来的）不记录。这个条件依赖 DFS 先走右子树的顺序。 - 空树处理： 先判断
if not root: return []。
框架提炼
BFS 每层取特定位置模板： 在层序遍历的基础上，可以在每层取出特定位置的节点（第一个、最后一个、第 k 个等）。
def level_extract(root):
if not root:
return []
res = []
q = deque([root])
while q:
for i in range(len(q)):
node = q.popleft()
if condition(i, len(q)): # 根据位置条件选择节点
res.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return resDFS 反向遍历模板： 当需要从某一侧观察树的节点时，调整 DFS 的访问顺序。
从右侧看：先右后左 (right → left)
从左侧看：先左后右 (left → right)
关联题目
- 102-二叉树的层序遍历 — BFS 模板题，右视图是层序遍历的一个简单变体。
- 515-在每个树行中找最大值 — 同样是层序遍历变体，每层取最大值而非最右值。
- 199-二叉树的左视图 — 本质相同，DFS 时先左后右即可（实际 LeetCode 无此题，但面试可能出现）。