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

示例 1：

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

输出：[1,3,4]

解释：

示例 2：

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

输出：[1,3,4,5]

解释：

示例 3：

输入：root = [1,null,3]

输出：[1,3]

示例 4：

输入：root = []

输出：[]

层序遍历

# 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

from collections import deque

class Solution:

    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:

        if not root:

            return []

        queue = deque()

        queue.append(root)

        ans = []

        while queue:

            level_length = len(queue)

            for _ in range(level_length):

                cur = queue.popleft()

                if cur.left:

                    queue.append(cur.left)

                if cur.right:

                    queue.append(cur.right)

            ans.append(cur.val)

        return ans  

一、题目分析

### 题目描述

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

### 核心理解

本题的核心需求是获取「二叉树每一层最右侧的节点值」，因为站在二叉树右侧，每一层只能看到最右边的那个节点。无论该节点是否有左子节点，只要它是当前层的最右侧节点，就需要被纳入结果。

关键突破口：利用层序遍历（广度优先搜索，BFS），遍历每一层的所有节点，记录每一层最后一个节点的值，即可得到右侧视图。

### 示例解析

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

二叉树分层为：第1层[1]、第2层[2,3]、第3层[5,4]；每一层最右侧节点分别为1、3、4，输出[1,3,4]。

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

二叉树分层为：第1层[1]、第2层[2,3]、第3层[4]、第4层[5]；每一层最右侧节点分别为1、3、4、5，输出[1,3,4,5]。

示例3：输入root = [1,null,3]

二叉树分层为：第1层[1]、第2层[3]；最右侧节点为1、3，输出[1,3]。

示例4：输入root = []（空树），无任何节点，输出[]。

二、解题思路

采用「层序遍历（BFS）」实现，核心思路是逐层遍历二叉树，记录每一层的最后一个节点值，具体步骤如下：

具体步骤：

1. 边界处理：如果根节点root为空，直接返回空列表（无任何节点可看）。

2. 初始化：使用双端队列deque（高效实现队列的入队、出队操作），将根节点入队；定义结果列表ans，用于存储每一层最右侧节点值。

3. 层序遍历循环：只要队列不为空，就继续遍历（队列中存储的是当前层的所有节点）。

4. 获取当前层长度：记录当前队列的长度level_length，该长度即为当前层的节点总数（用于区分不同层的节点）。

5. 遍历当前层节点：循环level_length次，依次弹出队列头部节点cur，同时将cur的左、右子节点（若存在）依次入队（保证下一层节点按顺序入队）。

6. 记录当前层最右侧节点：当循环结束时，最后一次弹出的节点cur即为当前层最右侧节点，将其值加入结果列表ans。

7. 重复上述步骤，直到所有层遍历完毕，返回结果列表ans。

三、代码解析

给定代码正是上述层序遍历思路的完整实现，逐行解析如下：

# 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

from collections import deque

class Solution:

    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:

        if not root:  # 边界处理：空树直接返回空列表

            return []

        queue = deque()  # 初始化双端队列，用于层序遍历的节点存储

        queue.append(root)  # 根节点入队，作为第一层的唯一节点

        ans = []  # 结果列表，存储每一层最右侧节点值

       

        while queue:  # 队列不为空，说明还有层未遍历

            level_length = len(queue)  # 获取当前层的节点总数

            # 遍历当前层的所有节点

            for _ in range(level_length):

                cur = queue.popleft()  # 弹出队列头部节点（先进先出）

                # 若当前节点有左、右子节点，依次入队（为下一层遍历做准备）

                if cur.left:

                    queue.append(cur.left)

                if cur.right:

                    queue.append(cur.right)

            # 循环结束后，cur是当前层最后一个节点（最右侧），将其值加入结果

            ans.append(cur.val)

        return ans  # 返回所有层的最右侧节点值

### 关键细节说明

• 双端队列deque的作用：相比普通列表，deque的popleft()操作是O(1)时间复杂度，而列表的pop(0)是O(n)，能提升层序遍历的效率。

• 层长度level_length的作用：精准区分每一层的节点，确保遍历完当前层所有节点后，才能记录最右侧节点，避免混淆不同层的节点。

• 子节点入队顺序：先左后右，不影响结果——因为无论左子节点是否存在，当前层最后一个弹出的节点，始终是当前层最右侧的节点（哪怕该节点只有左子节点，下一层的左子节点会成为下一层的节点）。

• 边界处理：空树直接返回空列表，避免后续队列操作报错，覆盖了示例4的场景。

四、复杂度分析

### 时间复杂度

时间复杂度为O(n)，其中n是二叉树的节点总数。因为层序遍历会遍历二叉树的每一个节点，每个节点入队、出队各一次，操作均为O(1)，整体时间复杂度由节点总数决定。

### 空间复杂度

空间复杂度为O(n)，最坏情况下（完全二叉树的最后一层），队列中会存储n/2个节点（完全二叉树最后一层节点数最多）；最好情况下（斜树），队列中最多存储1个节点，空间复杂度为O(1)。整体空间复杂度由队列的最大存储量决定，最坏为O(n)。

五、补充说明

1. 深度优先搜索（DFS）思路：也可以用DFS实现，优先遍历右子树、再遍历左子树，记录每一层第一次访问到的节点（即为该层最右侧节点）。相比BFS，DFS无需使用队列，但递归深度过大时可能出现栈溢出，适合节点数较少的二叉树。

2. 特殊场景注意：当某一层只有左子节点时（无右子节点），该左子节点就是当前层的最右侧节点，会被正常记录（例如：root = [1,2,null,3]，右侧视图为[1,2,3]）。