LeetCode LCR 046. 二叉树的右视图
目录
题目描述
题意分析
题目目标：站在树的右侧往左看，按从上到下的顺序返回能看到的节点值，本质上就是每一层最右边那个节点的值组成的数组。
核心约束：这里的"最右"是层内位置概念——同一层中水平位置最靠右的节点，而不是"沿右孩子一路走下去"的节点。当某层最右的节点是通过左孩子产生的时（右子树在这一层已经断掉），两种理解会给出完全不同的答案。
边界处理：树可能为空，需要返回空数组；只有一个节点时答案就是根值；某一层可能只有左孩子存在，它仍然是这一层的右视图节点。
实现取舍：答案的长度等于树高，每层只贡献一个值，因此遍历过程只需要能可靠地识别"每层的最后一个节点"，不需要保存整层内容。
解法：深度优先搜索
核心思路
暴力做法是先求树高，再按深度逐层扫描找出每层最右节点，遍历次数等于层数，代价 $O(nh)$，链状树退化成平方级，而且每次扫描做的都是重复功。
观察逐层推进的遍历顺序：如果每层的节点在容器中按从左到右排列，那么"层内最后一个出队的节点"就是右视图节点；但"最后一个"要靠下标计数才能识别。换一个角度会更省事——如果把入队顺序改成"先右孩子后左孩子"，那么每层在容器中就是从右到左排列，此时队首就是这一层最右的节点，取值时既不用计数也不用等到层末。
由此确定不变量：每轮外层循环开始时，容器q中恰好装着当前层的全部节点，且顺序是从右到左；因此q.peekFirst()就是本层的右视图节点，直接取值追加进答案。
内层循环按快照长度消费完整层，消费时依旧先右后左地把孩子入队，于是下一层在容器中同样保持从右到左的排列，不变量对下一轮继续成立。
解题步骤
- 先判空返回空数组。为什么必须显式处理：后续第一步就要取队首的
val，空树会让容器里唯一的元素是空指针，直接崩溃。- 根节点入队后进入外层循环，条件为容器非空。为什么这等价于"还有层未处理"：不变量保证容器里就是下一个待处理层，为空说明已经处理完最后一层。
- 每轮先执行
answer.add(q.peekFirst().val)，注意是"看"而不是"取出"。为什么可以在层还没消费时就取值：不变量已经保证队首是本层最右节点，它的身份与后续消费无关，提前取值可以省掉一个层内计数分支。- 用
for (int i = q.size(); i > 0; --i)固定本层消费个数。为什么必须快照：循环体内会往同一容器追加下一层节点，直接以q.size()为条件会把下一层混进本层，队首的层归属随之错乱。- 消费每个节点时先入队右孩子、再入队左孩子。为什么这个顺序是全部推理的地基：它保证下一层在容器中从右到左排列，"队首即最右"才成立；一旦写成先左后右，取的就变成了左视图。
- 循环结束返回
answer，其长度自然等于树高。为什么不会多也不会少：每层恰好触发一次取值，层数即树高。- 以
具体用例：树[1, 2, 3, 4, null, null, null, 5]（根 1；第二层 2、3；第三层 4 是 2 的左孩子，3 无孩子；第四层 5 是 4 的左孩子）走一遍。第一轮容器[1]，取队首得 1，入队顺序先右后左得到[3, 2]。第二轮容器[3, 2]，取队首得 3，消费 3 无孩子、消费 2 只有左孩子 4，容器变[4]，答案[1, 3]。第三轮容器[4]，取队首得 4，注意这一层最右的节点正是由左孩子产生的，答案[1, 3, 4]，入队 5。第四轮容器[5]，取得 5，答案[1, 3, 4, 5]。若按"一路走右孩子"的错误理解，第三层之后就断了，只能得到[1, 3]。
代码实现
// 核心实现：深度优先搜索，维护必要状态并避免重复处理。
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> answer = new ArrayList<>();
if (root == null) {
return answer;
}
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
answer.add(q.peekFirst().val);
for (int i = q.size(); i > 0; --i) {
TreeNode node = q.poll();
if (node.right != null) {
q.offer(node.right);
}
if (node.left != null) {
q.offer(node.left);
}
}
}
return answer;
}
}
// 核心实现：深度优先搜索，维护必要状态并避免重复处理。
func rightSideView(root *TreeNode) []int {
var answer []int
if root == nil {
return answer
}
q := []*TreeNode{root}
for len(q) > 0 {
answer = append(answer, q[0].Val)
for i := len(q); i > 0; i-- {
node := q[0]
q = q[1:]
if node.Right != nil {
q = append(q, node.Right)
}
if node.Left != nil {
q = append(q, node.Left)
}
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$。凭什么：每个节点恰好入队一次、出队一次，出队时只做至多两次入队判断；每层额外一次队首读取，层数不超过节点数。
- 空间复杂度：$O(w)$，
w为最大层宽，最坏为 $O(n)$；答案数组额外占 $O(h)$。凭什么：容器在任意时刻至多同时容纳相邻两层的部分节点。
关键点总结
- 调整入队顺序可以把"取层内最后一个"变成"取队首"，用结构上的安排替代运行时的计数，这是分层遍历里最实用的一个小技巧，左视图只需把先右后左改回先左后右。
- "最右"是层内位置而非路径概念，凡是视图类题目都要先把这一点确认清楚，否则解法从一开始就错。
- 层长度快照仍然是分层写法的命门，即便本题的取值发生在消费之前，快照缺失依然会让层与层的边界坍塌。
- 提前在层首取值而不是层末取值，让每轮循环只保留一个职责（取值/消费），代码分支更少也更难写错。
- 面试视角：面试官经常要求给出递归写法。递归时按"根、右子树、左子树"的顺序访问并携带深度，当
depth == answer.size()时说明这一深度第一次被触达，此时的节点必然是最右节点，直接追加。能主动对比两种写法的空间（递归 $O(h)$、迭代 $O(w)$），并说明它们在链状树与满树上的取舍，是这题的标准满分答法。
易错点总结
- 错误写法：入队顺序写成先左后右，取值仍取队首 → 树
[1, 2, 3]时返回[1, 2]，得到的是左视图。- 错误写法：把题意理解成沿右孩子一路走 → 树
[1, 2, 3, 4]（4 是 2 的左孩子，3 无孩子）时正确答案是[1, 3, 4]，该写法只得到[1, 3]，第三层被漏掉。- 错误写法：内层循环条件写成
i > 0 && !q.isEmpty()却用q.size()实时求值 → 树[1, 2, 3]时第二层节点被卷进第一层，答案退化成[1]。- 错误写法：漏掉
root == null判空 → 空树时q.peekFirst().val对空指针取值直接异常，Go 里则是q[0].Val触发 panic。- 错误写法：用
q.pollFirst()代替q.peekFirst()取值 → 队首节点被提前弹出却没有把它的孩子入队，树[1, 2, 3, null, null, 4]时第三层的 4 永远进不了容器，答案缺层。- 错误写法：把空孩子也入队 → 队首可能是空节点，取
val时崩溃；即使加判空跳过，空层也会让答案多出一项。- 错误写法：
answer.add(...)写在内层循环里 → 树[1, 2, 3]时第二层产生两个答案项，得到[1, 3, 2]，长度不再等于树高。- 错误写法：递归版用
depth <= answer.size()或不带等号的判断决定是否追加 → 每层会追加多次或一次都不追加，树[1, 2, 3]分别得到长度为 3 的数组或空数组。- 错误写法：递归版按"根、左子树、右子树"顺序访问却仍用
depth == answer.size()判定 → 每层第一次触达的是最左节点，返回的是左视图，树[1, 2, 3]得到[1, 2]。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| LCR 045. 找树左下角的值 | 中等 | 只取最深层的最左值，答案是单值而非数组 |
| LCR 044. 在每个树行中找最大值 | 中等 | 层内聚合规则是比大小而不是看位置 |
| 102. 二叉树的层序遍历 | 中等 | 需保留每层完整列表，考察分层结果的组织 |
| 103. 二叉树的锯齿形层序遍历 | 中等 | 层内方向逐层交替，入队顺序无法一次固定 |
| 662. 二叉树最大宽度 | 中等 | 需给节点附层序编号，空位也参与宽度计算 |
| 1302. 层数最深叶子节点的和 | 中等 | 只结算最深一层，可用覆盖式累加省去答案数组 |