LeetCode 199. 二叉树的右视图
题目描述
题意分析
从右侧看二叉树，同一深度只保留最靠右的节点，结果按深度从上到下排列。因此本题求的是每一层最右节点的值，既不是这一层的最大值，也不是所有右孩子的值。
不能只从根节点沿着右孩子走：右侧分支结束后，更深层仍可能存在左子树中的节点，它们在各自层上依然可见。空树返回空列表，其他情况下每个实际存在的层都恰好贡献一个节点。
解法：BFS 层序遍历
核心思路
[!blue]
答案按层产生，可以用队列逐层访问整棵树。每轮开始时，队列中恰好保存当前层的节点，并且从队首到队尾按从左到右排列；只要取出其中最后一个节点，就得到这一层的右视图。
这个顺序来自入队规则：先按从左到右的顺序处理父节点，再把每个父节点的左孩子、右孩子依次加入队尾。更靠左的父节点的孩子先入队，同一父节点的左孩子也在右孩子前面，因此下一层仍然从左到右排列。根节点单独成层，归纳下来，每层都能维持这个顺序。
遍历当前层时还会把下一层节点加入同一个队列，所以必须在本轮开始前记住
levelSize = queue.size()，并且只出队这levelSize个节点。这样新加入的孩子留给下一轮，最后一次出队的位置i == levelSize - 1才确实属于当前层的最右节点。
解题步骤
- 创建结果列表。若根节点为空，直接返回；否则把根节点加入队列。
- 每轮记录队列当前长度
levelSize，它就是本层节点数。- 连续取出
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)$，
n为节点数，每个节点只入队、出队一次。- 空间复杂度：$O(w)$，
w为二叉树最大宽度。队列可能同时保留本层剩余节点和下一层已入队节点，但数量仍为 $O(w)$；不计返回结果。
关键点总结
[!green]
- 右视图由每层的结构位置决定，与节点数值大小无关。
- 从左到右处理父节点、先左后右加入孩子，保证下一层也从左到右。
- 先固定层大小，再处理这一层，避免新入队的孩子干扰当前层的边界。
解法：右优先 DFS
核心思路
[!blue]
另一种做法不显式分层，而是让深度优先遍历优先进入右子树。对于任意固定深度，右子树中处于该深度的节点会早于左子树中的节点被访问；在每个子树内部也遵循相同规则。因此，某一层第一次被访问到的节点，就是这一层最靠右的节点。
用
depth表示当前节点深度，根节点深度为0；结果列表按深度保存已找到的右视图。当depth == res.size()时，说明前面的层已经有答案，而这一层还没有答案，把当前节点加入结果即可。如果depth小于结果长度，说明这一层已经记录了更靠右的节点，不能覆盖。记录之后，先递归右孩子，再递归左孩子。右子树不够深时，左子树仍会继续向下探索；一旦到达此前没有访问过的深度，就会补上该层答案。因此右优先只是决定同层谁先被看到，并不意味着忽略左子树。
解题步骤
- 创建本次调用独立的结果列表，从根节点和深度
0开始递归。- 当前节点为空时结束该分支；非空时，若
depth等于结果长度，就记录当前节点值。- 先递归右孩子，再递归左孩子，两次调用的深度都为
depth + 1。- 递归完成后返回结果；节点只会在其所在深度尚无答案时被记录。
代码实现
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
collectRightmost(root, 0, res);
return res;
}
private void collectRightmost(TreeNode node, int depth, List<Integer> res) {
if (node == null) {
return;
}
if (depth == res.size()) {
res.add(node.val);
}
collectRightmost(node.right, depth + 1, res);
collectRightmost(node.left, depth + 1, res);
}
}
func rightSideView(root *TreeNode) []int {
res := make([]int, 0)
var dfs func(*TreeNode, int)
dfs = func(node *TreeNode, depth int) {
if node == nil {
return
}
if depth == len(res) {
res = append(res, node.Val)
}
dfs(node.Right, depth+1)
dfs(node.Left, depth+1)
}
dfs(root, 0)
return res
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点访问一次，记录与深度判断均为常数操作。
- 空间复杂度：$O(h)$，
h为树高，来自递归调用栈；不计返回结果。平衡树的栈深为 $O(\log n)$，退化为链时为 $O(n)$。
关键点总结
[!green]
- 右优先 DFS 保证每层第一次访问到的节点最靠右。
depth == res.size()同时判断这一层是否已有答案，并保持结果按深度排列。- 两棵子树都需要遍历，左子树负责补上右子树未覆盖的深度。
- BFS 保存待处理的一层节点，DFS 保存当前递归路径，额外空间分别取决于树宽和树高。
易错点总结
[!yellow]
- 只沿右孩子向下，会漏掉右侧分支结束后左子树中更深的可见节点；两种遍历都必须覆盖整棵树。
- BFS 在内层循环中动态读取队列长度，会把当前层与下一层混在一起，无法准确找到本层最后一个节点。
- BFS 若改成先右后左入队，就应取每层第一个节点；仍取最后一个会得到左视图。
- DFS 先访问左子树却记录每层第一个节点，会得到左视图；访问顺序必须与记录规则配套。
- DFS 对同一深度反复覆盖结果，会让较晚访问的左侧节点覆盖已经记录的右侧节点。
- 空树应直接返回空结果，不能把空节点加入不接受空值的队列。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 515. 在每个树行中找最大值 | 中等 | 同样每层输出一个值，但最大值与最右节点无关，不能混淆选择条件。 |
| 513. 找树左下角的值 | 中等 | 同样取层的边界节点，原题只保留最深层最左值，本题保留每层最右值。 |
| 补充题 198. 由前序和中序遍历求二叉树右视图 | 中等 | 都逐层选取最右节点；补充题先依据两种遍历结果重建树。 |
| 补充题 196. 二叉树左视图 | 中等 | 都按层遍历二叉树；本题取每层最右节点，补充题取最左节点。 |
| 102. 二叉树的层序遍历 | 中等 | 按层遍历并在同一层内聚合；本题每层只取最右节点，该题保留每层全部节点。 |
| 103. 二叉树的锯齿形层序遍历 | 中等 | 按层遍历并在同一层内聚合；本题每层只取最右节点，该题交替调整每层输出方向。 |
| 107. 二叉树的层序遍历 II | 中等 | 按层遍历并在同一层内聚合；本题每层只取最右节点，该题把自顶向下的层结果反转。 |