二叉树的右视图（Binary Tree Right Side View）

题目描述
给定一棵二叉树的根节点 root，想象你站在二叉树的右侧。返回从右侧所能看到的节点值，按照从上到下的顺序。换句话说，你需要返回每一层最右边的节点值。

例如，对于二叉树：

     1
    / \
   2   3
    \   \
     5   4

从右侧看，你能看到的节点是 1, 3, 4，所以应返回 [1, 3, 4]。

解题过程循序渐进讲解

这个问题本质上是要获取二叉树每一层的最右边节点。核心思路是进行层序遍历，但在遍历每一层时，我们只需记录该层最后一个访问到的节点值。下面我会详细分解步骤。

步骤1：理解问题与核心思路

• 二叉树每一层可能有多个节点，但从右侧看过去，每一层你只能看到最右边的那个节点（如果该层有多个节点，左侧的会被右侧的挡住）。
• 因此，我们需要一种能按层遍历二叉树，并能识别每层最后一个节点的方法。
• 层序遍历通常使用广度优先搜索（BFS），利用队列实现。在BFS过程中，我们可以通过记录每层的节点数量，来逐层处理。

步骤2：BFS层序遍历的基本框架
层序遍历的标准BFS写法是：

1. 初始化一个队列，将根节点入队（如果根不为空）。
2. 当队列不为空时，进行循环：
   • 获取当前队列的长度 size，这个 size 就是当前层的节点个数。
   • 用循环处理这 size 个节点：依次出队，并将它们的非空子节点入队。

在这个问题中，我们只需要在每一层的内部循环中，记录最后一个出队的节点值。

步骤3：在BFS中收集右视图节点
具体做法：

1. 创建结果列表 right_view。
2. 创建队列，初始化放入根节点（如果根不为空）。
3. 进入队列不为空的外层循环：
   • 获取当前层的节点数 level_size = queue.size()。
   • 进入内层循环，迭代 level_size 次：
     • 从队列中出队一个节点 node。
     • 如果这是当前层的最后一个节点（即内层循环的当前迭代是第 level_size 次），则将 node.val 加入 right_view。
     • 如果 node 有左子节点，将其入队。
     • 如果 node 有右子节点，将其入队。
4. 返回 right_view。

步骤4：举例说明
以前面的例子：

     1
    / \
   2   3
    \   \
     5   4

BFS过程：

• 初始队列：[1]。
• 第一层：level_size = 1，处理节点1，它是该层最后一个（也是唯一一个），记录1。入队其子节点2、3，队列变为[2, 3]。
• 第二层：level_size = 2，先处理节点2，它不是最后一个（因为后面还有节点3），不记录。入队其右子5，队列变为[3, 5]。然后处理节点3，它是该层最后一个，记录3。入队其右子4，队列变为[5, 4]。
• 第三层：level_size = 2，处理节点5，不是最后一个，不记录。入队其子节点（无）。队列变为[4]。然后处理节点4，是最后一个，记录4。队列为空，结束。
• 结果：[1, 3, 4]。

步骤5：复杂度分析

• 时间复杂度：O(N)，其中 N 是二叉树的节点数。每个节点恰好入队、出队一次。
• 空间复杂度：O(W)，其中 W 是树的最大宽度（即最宽一层的节点数），在最坏情况下（完全二叉树底层）约为 N/2，即 O(N)。

步骤6：DFS替代方案（扩展思路）
除了BFS，也可以用DFS（深度优先搜索）来解决，思路是：

• 按照“根节点 -> 右子树 -> 左子树”的顺序遍历（这样可以保证每层先访问最右边的节点）。
• 维护一个变量 current_depth 表示当前深度，如果 current_depth 第一次达到某个深度，则当前节点就是该层最右节点（因为我们是先右后左遍历）。
• 递归或迭代实现均可，但递归代码更简洁。DFS时间复杂度也是 O(N)，空间复杂度在最坏情况下（树退化成链）为 O(N)。

总结
二叉树的右视图问题，核心是通过层序遍历（BFS）记录每一层的最后一个节点。关键在于利用队列进行广度优先遍历，并在每层处理时通过固定循环次数来分层，从而识别每层末尾节点。掌握这个方法后，类似问题如“左视图”、“边界视图”等都可以举一反三。