LeetCode LCR 046. 二叉树的右视图
题目描述
题意分析
右视图由每一层最右侧节点的值组成，按深度从上到下返回。这个节点可能来自左子树，只沿右孩子一直向下并不能得到完整答案；空树返回空列表。
解法：BFS 先右后左遍历
核心思路
[!blue]
用 BFS 逐层处理，并让同层节点在队列中按从右到左排列。这样每轮开始时，队首就是本层最右节点，直接记录它的值即可，不必保存这一层的全部值。
根节点单独成层，显然满足这个顺序。处理一层时，父节点已经从右到左出队，再对每个父节点先加入右孩子、后加入左孩子，就会让下一层同样从右到左排列。缺少某个孩子只会少加入一个节点，不会改变其余节点的相对顺序。
每轮必须先固定当前队列长度，只消费这些节点。遍历中追加的是下一层节点，不能把它们继续算进本层。消费完固定数量后，队列恰好变成下一层，层序和队首取值的依据就能一直保持。
解题步骤
- 根节点为空时直接返回空列表，否则将根节点入队。
- 每轮读取队首节点的值加入答案，先不将它弹出，它仍需参与本层的孩子扩展。
- 记录本层节点数，并恰好出队这么多个节点；每次先加入非空右孩子，再加入非空左孩子。
- 队列为空时所有层都已处理，返回答案。
一层只有一个节点时，它自然就是队首；右子树没有更深节点时，左子树剩余节点仍会进入后续层。因此每层恰好贡献一个值，答案长度等于树高。
代码实现
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(h)$，$h$ 为树高。
关键点总结
[!green]
- 先右后左入队和每层取队首需要配合使用。
- 固定本层节点数，才能把本层处理与下一层入队分开。
- 所有节点都要正常扩展，只有记录答案时每层选一个。
易错点总结
[!yellow]
- 当前实现先右后左入队，每层队首才是最右节点；改入队方向就要同步改取值规则。
- 读队首时使用 peek，不提前弹走尚未扩展孩子的节点。
- 空树返回空列表，一层只记录一个值，不能只沿原树右孩子走到底。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 515. 在每个树行中找最大值 | 中等 | 同样每层输出一个值，但最大值与最右节点无关，不能混淆选择条件。 |
| 513. 找树左下角的值 | 中等 | 同样取层的边界节点，原题只保留最深层最左值，本题保留每层最右值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！