199. 二叉树的右视图

题目链接：199. 二叉树的右视图

题目描述

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

核心思考：层序遍历（BFS）

想要看到二叉树的“右视图”，本质上就是获取每一层中最右侧的那个节点。

1. 层序遍历：通过层序遍历（BFS），我们可以逐层访问二叉树。使用队列 deque 来维护当前层的节点。
2. 提取层级最右节点：在逐层处理时，对于每一层，队列中最后入队的元素（即当前层的最后一个元素）就是由于我们从左向右压入节点，而位于最右侧的节点。
3. 流程：
   • 记录当前队列的长度（即当前层的节点总数）。
   • 将队列末尾的元素加入结果集 ans。
   • 依次弹出当前层的所有节点，并将其左右子节点（如果存在）按序压入队列中，供下一层遍历。

这种方法能够保证我们按从上到下的顺序，精准捕捉每一层“最右侧”的视野。

解题思路 (Python)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        ans = []
        q = deque([root])
        while q:
            # 队列中的最后一个元素即为当前层最右侧的节点
            ans.append(q[-1].val)
            # 遍历并处理当前层的所有节点
            for _ in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return ans

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是二叉树的节点数。每个节点都会且仅会进入队列并被处理一次。
• 空间复杂度：$O(N)$，在最坏情况下（例如完全二叉树），队列中最多会同时存在层级规模的节点（约为 $N/2$）。