#199. 二叉树的右视图

LeetCode 原题链接

#题目描述

站在二叉树右侧，返回从上到下能看到的节点值。

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

#题型判断

右视图不是简单沿着 right 指针向下走：某层没有右孩子时，左子树中的节点也可能被看到。本质是取得每一层最右侧的节点，因此使用层序 BFS。

#核心思路

按从左到右的顺序处理每层节点。每一层中最后访问到的节点，就是从右侧能看到的节点。

第 1 层：[1]       → 最右侧是 1
第 2 层：[2, 3]    → 最右侧是 3
第 3 层：[5, 4]    → 最右侧是 4

因此在每层开始时先固定当前层节点数 levelSize。当 i === levelSize - 1 时，说明当前节点是这一层最后一个节点，将它加入答案。

levelSize 必须在进入内层循环之前固定下来，因为处理当前层节点时，会不断把下一层节点加入队列。如果不先固定当前层大小，就会把下一层节点也混进当前层。

#代码实现

var rightSideView = function (root) {
  if (!root) return [];

  const result = [];
  const queue = [root];
  let head = 0;

  while (head < queue.length) {
    const levelSize = queue.length - head;

    for (let i = 0; i < levelSize; i++) {
      const node = queue[head++];

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);

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

  return result;
};

#复杂度分析

• 时间复杂度：O(n)，每个节点只会被访问一次。

• 空间复杂度：O(n)。

  当前实现使用 head 指针模拟出队，queue 中访问过的节点不会被删除，最坏情况下会保存所有节点。如果使用真正的队列结构，只看遍历过程中的待处理节点，辅助空间可以理解为 O(w)，其中 w 是二叉树最大层宽。

#边界与易错点

• 空树返回 []。
• 不要只遍历右孩子。
• levelSize 要在每一层开始时固定，不能在循环过程中动态读取 queue.length。
• 若改成“右孩子先入队”，应记录每层第一个节点；入队顺序和取值位置必须配套。
• 使用 head 指针时，循环条件应该是 head < queue.length，不能只判断 queue.length > 0。