LeetCode 199. 二叉树的右视图
目录
题目描述
题意分析
站在树的右侧向左看，被前面的节点挡住的都看不见，题目要的是从上到下依次能看到的那些节点值。
把这句话翻译成精确定义：对每一个深度，只有该深度上最靠右的那个节点是可见的，因为同层其他节点都被它挡住；而不同深度的节点不会互相遮挡。所以答案的长度恰好等于树的高度，第
d个元素就是深度d上最右节点的值。这一步翻译是全题的关键，剩下的只是「怎么按深度分组并取每组的最后一个」。约束里透露的信号是：题目按深度组织答案，说明必须掌握每个节点的深度信息，而且必须能区分「同层」与「跨层」。这提示两种自然的组织方式——要么按深度一批一批地处理节点，要么在遍历中把深度当参数传下去。节点总数上限一万，$O(n)$ 的一趟遍历完全够用，不需要任何预处理或缓存。
需要留意的边界情形：空树要返回空列表；只有一个节点时答案就是根；最容易被忽略的是树可以很不规则——某一层的最右节点未必是根一路向右走到的那个节点，如果右子树在某个深度就断了，而左子树还在往下延伸，那么更深层的可见节点来自左子树。换句话说，答案不是「从根沿右孩子走出的一条链」。
解法：BFS 层序遍历
核心思路
层序遍历会按深度、从左到右访问节点。每轮固定当前层的节点数，并记录这一层最后出队的节点，它就是从右侧能看到的节点。
解题步骤
- 空树直接返回空结果，非空时将根节点入队。
- 每轮先记录
levelSize，只处理当前层的这些节点。- 按先左后右的顺序将非空孩子入队。
- 将本层最后一个节点值加入结果，直到队列为空。
代码实现
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
if (i == levelSize - 1) {
res.add(node.val);
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return res;
}
}
func rightSideView(root *TreeNode) []int {
res := make([]int, 0)
if root == nil {
return res
}
queue := []*TreeNode{root}
for len(queue) > 0 {
levelSize := len(queue)
for i := 0; i < levelSize; i++ {
node := queue[0]
queue = queue[1:]
if i == levelSize-1 {
res = append(res, node.Val)
}
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
}
return res
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点入队、出队各一次。
- 空间复杂度：$O(w)$，
w为二叉树的最大宽度；不计返回结果。
关键点总结
- 右视图等价于每层最右节点，不是沿右孩子形成的链。
levelSize必须在处理本层前固定。- 先左后右入队时，本层最后出队的节点最靠右。
易错点总结
- 只沿右孩子向下会漏掉左子树中更深层的可见节点。
- 在内层循环中动态读取队列长度，会混淆当前层与下一层。
- 先右后左入队却仍取本层最后一个节点，会得到左视图。
- 空树未提前返回，可能把空节点加入不接受空值的队列。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 102. 二叉树的层序遍历 | 中等 | 每层要输出全部节点而不是只留最右一个，答案是二维数组 |
| 103. 二叉树的锯齿形层序遍历 | 中等 | 层内顺序需要按奇偶深度交替翻转，多出一个方向状态 |
| 107. 二叉树的层序遍历 II | 中等 | 层与层之间的输出顺序自底向上，需要头插或最终整体反转 |
| 429. N 叉树的层序遍历 | 中等 | 孩子个数不固定，入队要遍历 children 列表而非固定的左右两个 |
| 513. 找树左下角的值 | 中等 | 答案是单个值而非每层一个，且取的是最深层的最左侧节点 |
| 515. 在每个树行中找最大值 | 中等 | 每层取的是数值最大者而不是位置最右者，需要层内比较而非看下标 |
| 637. 二叉树的层平均值 | 简单 | 每层要累加求平均，涉及浮点除法与求和溢出，不能只保留一个节点 |
| 662. 二叉树最大宽度 | 中等 | 空位也计入宽度，必须给节点编号来度量层内跨度，队列里要带下标 |
| 958. 二叉树的完全性检验 | 中等 | 空节点也要入队，靠「第一个空节点之后是否还有实节点」判定，答案是布尔值 |
| 1302. 层数最深叶子节点的和 | 中等 | 只保留最深一层的和，每进入新层要把累加结果清零重来 |
| LCR 044. 在每个树行中找最大值 | 中等 | 与 515 同题换号，聚合方式由「取最右」换成「取最大」 |
| LCR 045. 找树左下角的值 | 中等 | 与 513 同题换号，只需最后一层的第一个节点，可用「反向入队取末元素」简化 |
| LCR 046. 二叉树的右视图 | 中等 | 与本题完全同题，仅题号与页面不同，可直接复用两份代码 |
| 剑指 Offer 32 - I. 从上到下打印二叉树 | 中等 | 输出压平成一维数组且不区分层，因此完全不需要 levelSize 快照 |
| 剑指 Offer 32 - II. 从上到下打印二叉树 II | 简单 | 等价于 102，练的是把「层内只留一个」放宽成「层内全留」 |
| 剑指 Offer 32 - III. 从上到下打印二叉树 III | 中等 | 等价于 103，额外要处理方向翻转，用双端队列可以免去反转 |
| 面试题 04.03. 特定深度节点链表 | 中等 | 每层要串成一条链表返回，层内遍历时需要维护链表尾指针而不是只取一个值 |