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

题目 / Problem

中文： 给定一棵二叉树的根节点 root，想象自己站在树的右侧，返回从上到下能够看到的节点值。

English: Given the root of a binary tree, imagine standing on its right side. Return the values of the visible nodes ordered from top to bottom.

示例 / Examples

Example 1

Input:  root = [1,2,3,null,5,null,4]
Output: [1,3,4]

每一层最右侧的节点依次是 1、3 和 4。
The rightmost nodes at each level are 1, 3, and 4.

Example 2

Input:  root = [1,2,3,4,null,null,null,5]
Output: [1,3,4,5]

节点 4 和 5 虽然位于左子树，但它们所在深度没有更靠右的节点遮挡，因此仍然可以从右侧看到。
Although nodes 4 and 5 belong to the left subtree, no nodes lie farther right at their depths, so they are still visible from the right.

Example 3

Input:  root = [1,null,3]
Output: [1,3]

Example 4

Input:  root = []
Output: []

约束 / Constraints

• 节点数量在 [0, 100] 范围内。
  The number of nodes is in the range [0, 100].
• -100 <= Node.val <= 100

解题思路：层序遍历 / Approach: Level-Order Traversal

从树的右侧看，每一层只能看到该层最右边的节点。
From the right side, only the rightmost node of each level is visible.

因此，可以使用广度优先搜索（BFS）逐层遍历二叉树：
Use breadth-first search (BFS) to traverse the tree level by level:

1. 将根节点加入队列。
   Add the root to a queue.
2. 记录当前层的节点数量 levelSize。
   Record the number of nodes in the current level as levelSize.
3. 依次取出该层的所有节点，并将其左右子节点加入队列。
   Remove every node in the level and enqueue its children.
4. 当前层最后取出的节点就是该层最右侧节点，将其值加入结果。
   The final node removed from the level is its rightmost node, so add its value to the result.

队列状态 / Queue State

如果每层按照从左到右的顺序入队：
When each level is enqueued from left to right:

Level 0: [1]       → 记录 1 / record 1
Level 1: [2,3]     → 记录 3 / record 3
Level 2: [5,4]     → 记录 4 / record 4

不需要保存完整的二维层序遍历结果，只需在遍历每层时记录最后一个节点。
There is no need to store the complete two-dimensional level-order traversal; record only the last node of each level.

JavaScript 实现：BFS / JavaScript Implementation: BFS

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *   this.val = val ?? 0;
 *   this.left = left ?? null;
 *   this.right = right ?? null;
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
function rightSideView(root) {
  if (root === null) {
    return [];
  }

  const result = [];
  let currentLevel = [root];

  while (currentLevel.length > 0) {
    const nextLevel = [];

    for (let i = 0; i < currentLevel.length; i++) {
      const node = currentLevel[i];

      if (node.left !== null) {
        nextLevel.push(node.left);
      }

      if (node.right !== null) {
        nextLevel.push(node.right);
      }

      if (i === currentLevel.length - 1) {
        result.push(node.val);
      }
    }

    currentLevel = nextLevel;
  }

  return result;
}

这里使用 currentLevel 和 nextLevel 分层保存节点，避免调用 shift()。JavaScript 数组的 shift() 可能需要移动剩余元素，频繁使用会增加额外开销。
The implementation stores nodes in currentLevel and nextLevel, avoiding shift(). JavaScript's shift() may move the remaining elements and add unnecessary overhead when called repeatedly.

执行过程 / Walkthrough

以 Example 1 为例：
For Example 1:

    1
   / \
  2   3
   \   \
    5   4

另一种方法：右侧优先 DFS / Alternative: Right-First DFS

也可以按照“根节点 → 右子树 → 左子树”的顺序进行深度优先搜索。
Depth-first search can also traverse in root-right-left order.

由于每一层先访问右侧节点，当 depth === result.length 时，说明这是该深度第一次访问到的节点，也就是右视图中可见的节点。
Because right-side nodes are visited first, depth === result.length means this is the first node reached at that depth and therefore the visible node.

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
function rightSideView(root) {
  const result = [];

  function dfs(node, depth) {
    if (node === null) {
      return;
    }

    if (depth === result.length) {
      result.push(node.val);
    }

    dfs(node.right, depth + 1);
    dfs(node.left, depth + 1);
  }

  dfs(root, 0);
  return result;
}

为什么不能只沿右子节点遍历？ / Why Not Follow Only Right Children?

右视图中的节点不一定都在右子树中。如果某一层没有右侧节点，左子树中最靠右的节点仍然可见。
Visible nodes do not necessarily belong to the right subtree. If a level has no node on the right, the rightmost node from the left subtree remains visible.

例如：
For example:

    1
   /
  2
 /
3

右视图是 [1,2,3]，但根节点没有任何右子节点。
The right-side view is [1,2,3], even though the root has no right child.

复杂度 / Complexity

设树中有 n 个节点，树高为 h，最大层宽为 w。
Let the tree contain n nodes, have height h, and maximum width w.

BFS

• 时间复杂度 / Time: O(n)
• 辅助空间 / Auxiliary space: O(w)，队列最多保存一层附近的节点。
  O(w) for nodes around the widest level in the queue.

DFS

• 时间复杂度 / Time: O(n)
• 辅助空间 / Auxiliary space: O(h)，用于递归调用栈。
  O(h) for the recursive call stack.

返回结果包含每一层的一个节点，需要 O(h) 结果空间。
The returned result contains one node per level and uses O(h) output space.

易错点 / Common Pitfalls

• 空树应返回空数组 []。
  Return [] for an empty tree.
• 右视图是每一层最右侧的节点，不是只沿着 right 指针向下走。
  The right-side view contains the rightmost node at each level, not only nodes reached by following right pointers.
• BFS 中必须区分 currentLevel 和 nextLevel，否则新加入的子节点可能被错误地算入同一层。
  In BFS, keep currentLevel and nextLevel separate so newly discovered children are not counted in the same level.
• DFS 必须先访问右子树，再访问左子树。
  DFS must visit the right subtree before the left subtree.
• DFS 中只在该深度第一次出现时加入节点，即 depth === result.length。
  In DFS, add a node only on the first visit to that depth: depth === result.length.