LeetCode 199. 二叉树的右视图

◎

本节目标

用层序遍历记录每层从左到右处理的最后一个节点。

这道题是遍历与层序视角的层序信息提取：从右侧看到的并非“每层最靠右的指针”，而是该层从左到右遍历中的最后一个实际节点。

查看 LeetCode 原题

朴素思路与瓶颈

可以为每层保存完整数组，再取最后一个元素，但这些中间数组并非答案所需。更直接的方式是在遍历该层时识别最后一次出队。

核心不变量

进入一层时固定 levelSize。本轮索引等于 levelSize - 1 的节点，是当前层从左到右的最后一个节点；把它加入答案。孩子只会进入下一层队列，不能影响本轮最后一个位置。

正确性依据

层序队列保证同层节点按从左到右出队。固定大小循环的最后一次迭代因此对应当前层最右的实际节点。对每一层记录一次该节点，得到完整右视图。

代码实现

C++

C++17

class Solution {
public:
    std::vector<int> rightSideView(TreeNode* root) {
        std::vector<int> answer;
        if (root == nullptr) {
            return answer;
        }

        std::queue<TreeNode*> nodes;
        nodes.push(root);
        while (!nodes.empty()) {
            int levelSize = static_cast<int>(nodes.size());
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = nodes.front();
                nodes.pop();
                if (i == levelSize - 1) {
                    answer.push_back(node->val);
                }
                if (node->left != nullptr) {
                    nodes.push(node->left);
                }
                if (node->right != nullptr) {
                    nodes.push(node->right);
                }
            }
        }
        return answer;
    }
};

Python

Python 3

from collections import deque
from typing import Optional


class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> list[int]:
        if root is None:
            return []

        answer: list[int] = []
        nodes = deque([root])
        while nodes:
            level_size = len(nodes)
            for index in range(level_size):
                node = nodes.popleft()
                if index == level_size - 1:
                    answer.append(node.val)
                if node.left is not None:
                    nodes.append(node.left)
                if node.right is not None:
                    nodes.append(node.right)
        return answer

复杂度分析

仍需检查每个节点一次，时间复杂度为 O(n)。队列最多保存最大层宽，额外空间为 O(w)；答案额外占用 O(h)。

易错点

• 把每层第一个节点误当作右视图，得到左视图。
• 从右到左入队却仍沿用“最后一个”判断，破坏了顺序假设。
• 依赖节点是否有右孩子；左链的节点同样可能出现在右视图中。

模式迁移

按层取首、尾、最大值或计数都遵循同一层边界；题目变化只影响每层的常数次记录动作。