🔗 二叉树的右视图

题目来源：199. 二叉树的右视图 – 力扣（LeetCode）

---

📌 题目描述

给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

即：从右往左看时，每层只能看到最右边的那个节点。

---

✅ 示例解析

示例 1：

输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]

解释：

• 第 0 层：[1] → 右侧看到 1
• 第 1 层：[2,3] → 右侧看到 3
• 第 2 层：[5,4] → 右侧看到 4

示例 2：

输入：root = [1,2,3,4,null,null,null,5]
输出：[1,3,4,5]

解释：
树向左倾斜很深，但每层最右节点依次为 1 → 3 → 4 → 5。

示例 3：

输入：root = [1,null,3]
输出：[1,3]

示例 4：

输入：root = []
输出：[]

---

⚠️ 提示

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

---

💡 解法：层序遍历（BFS）—— O(n) 时间，O(w) 空间

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        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) {
                    result.add(node.val);
                }

                // 将下一层节点加入队列（先左后右，保证顺序）
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }

        return result;
    }
}

✅ 关键点：每层遍历时，只取最后一个出队的节点，即为该层最右侧可见节点。

---

📊 复杂度分析

• 时间复杂度：O(n)
  每个节点恰好被访问一次，总共有 n 个节点。
• 空间复杂度：O(w)
w 是二叉树的最大宽度（即某一层最多节点数）。
  • 最坏情况（完全二叉树底层）：w ≈ n/2 → O(n)
  • 最好情况（链表）：w = 1 → O(1)

---

🧩 解题思路

为什么用 BFS（层序遍历）？

• “右视图”本质上是按层取最右节点，天然契合按层处理的 BFS。
• DFS 也可实现（记录深度，只保留每层第一次访问的右节点），但 BFS 更直观。

算法步骤：

1. 初始化队列，将根节点入队。
2. 当队列非空时，处理当前整层：
   • 记录当前层节点数 size。
   • 遍历 size 次，依次出队：
     • 若是第 size 个（即最后一个），加入结果列表。
     • 将其左右子节点（若存在）入队，供下一层使用。
3. 返回结果列表。

为什么先加左子节点，再加右子节点？

• 因为我们需要从左到右遍历当前层，才能确保最后一个节点是最右边的。
• 如果先加右再加左，虽然也能取到最后一个，但不符合常规层序逻辑，且可能影响其他变种题。