二叉树的右视图
Binary Tree Right Side View
从右侧看二叉树，返回每一层最右边节点的值（从上到下）。
在力扣中练习题目描述
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1：
输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]
解释：
示例 2：
输入：root = [1,2,3,4,null,null,null,5]
输出：[1,3,4,5]
解释：
示例 3：
输入：root = [1,null,3]
输出：[1,3]
示例 4：
输入：root = []
输出：[]
提示:
- 二叉树的节点个数的范围是
[0,100] -100 <= Node.val <= 100
解题思路
层序 BFS · 每层最后一个
逐层出队，记录本层最后一个节点
右视图就是每一层最右边的节点。层序遍历时，每轮先锁定当前层的节点数 sz，把这层的节点依次出队，第 sz 个（下标 sz-1）就是该层最右节点。
根节点 5 入队；队列里现在只有第一层。
关键是不能只看“右孩子”：如果右子树很浅、左子树更深，下一层的最右节点可能来自左子树。
自拟树第 3 层最右是 9，但第 4 层来自左子树的深处：2 和 6。逐层看队尾才能得到 [5,8,9,6]。
每个节点入队出队一次，时间 O(n)，空间 O(宽度)。
易错点
- 一直沿 right 指针走：左子树更深时会漏掉层。
- 不锁定 sz：新入队的孩子被当成当前层，层号错乱。
- 把每层第一个出队节点当最右：队首其实是最左。
DFS · 先右后左
每层第一次到达的节点，就是该层最右
时间同为 O(n)，但依赖“先访问右子树”的顺序；BFS 的层语义更直接。
先递归右子树、再递归左子树。这样对于每一层，最先到达的一定是最右边的节点。
用一个 depth 参数记录层号；如果 depth == res.size()，说明这一层还没有记录过，当前节点就是该层最右，加入结果。之后再遇到同层节点时 depth < res.size()，直接跳过。
这种写法不需要队列，空间是 O(h)；代价是理解“第一次到达”的含义，而且必须先右后左，顺序反了会得到左视图。
- 1空节点返回。
- 2该层第一次到达时记录当前值。
- 3先递归右子树。
- 4再递归左子树。
易错点
- 先左后右：得到的是左视图。
- 用 depth == res.size() - 1 判断：第一层就会漏记。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
root = [5,3,8,1,null,7,9,null,2,null,6]空树直接返回；根入队，从第 1 层开始逐层处理。
查看 C++ 代码
延伸阅读
- 右视图、左视图、每层平均值都可以由层序模板改造，关键是明确“层的边界”。
- DFS 版利用了遍历顺序和层号的对应关系，适合不想写队列的场合。