82.二叉树的右视图
题目
给定一个二叉树的 根节点 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
思路
给你一颗二叉树，想象你站在树的右边往左看，把你能看到的节点从上往下依次返回。
1 你站在右边 → 👁
/ \
2 3 看到：1、3、4
\ \
5 4 （5 被 4 挡住了）
翻译成一句人话: 每一层最右边的那个节点，从上到下排成一列。
先掐死一个坑: 一路往右走是错的，很多人第一个反应是: 从根开始不停node = node.right，走到底就是右视图。 这在上面那棵树恰好能过，但换成下面这棵树就崩了:
1
/ \
2 3 右子树到第 2 层就断了
/
4 第 3 层只有一个 4，它站在最右边
- 一路往右：1 → 3 → null，得到 [1, 3] ❌
- 正确答案：[1, 3, 4] ✅
因为「某一层最右边的节点」不一定挂在右子树上。 当右子树比左子树矮时，下面几层的最右节点其实来自左子树。
所以必须真的按"层"去看，不能顺着一条路径走。
思路一: 层序遍历（BFS）
既然答案就是每层最后一个节点，那就一层一层的遍历，每层只记最后那个。
标准做法是BFS，但有个必备的技巧: 在处理每一层之前，先把队列当前的长度记下来。
class Solution {
/**
* 二叉树的右视图 —— BFS 层序遍历版
*
* 核心思想：右视图 = 每一层最右边的节点。
* 按层遍历，每层只把最后出队的那个节点记进答案。
*
* 时间复杂度 O(n)：每个节点进出队列各一次
* 空间复杂度 O(w)：w 为树的最大宽度，最坏（满二叉树最后一层）约 n/2
*/
fun rightSideView(root: TreeNode?): List<Int> {
val res = mutableListOf<Int>()
if (root == null) {
return res
}
// ArrayDeque 当队列用：尾进头出
val queue = ArrayDeque<TreeNode>()
queue.addLast(root)
while (queue.isNotEmpty()) {
// ⚠️ 关键：先把这一层的节点数固定下来。
// 循环体里会往队尾塞下一层节点，queue.size 会变，不能直接当循环条件用。
val levelSize = queue.size
for (i in 0 until levelSize) {
val node = queue.removeFirst()
// 本层的最后一个出队节点，就是最右边那个 → 记入答案
if (i == levelSize - 1) {
res.add(node.`val`)
}
// 先左后右入队，保证下一层在队列里也保持"左→右"的顺序，
// 这样下一层最后出队的仍然是最右节点
if (node.left != null) {
queue.addLast(node.left!!)
}
if (node.right != null) {
queue.addLast(node.right!!)
}
}
}
return res
}
}
复杂度
- 时间复杂度:
- 空间复杂度:
- 邮箱 ：charon.chui@gmail.com
- Good Luck!