难度: Medium
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4] 输出: [1,3,4]
示例 2:
输入: [1,null,3] 输出: [1,3]
示例 3:
输入: [] 输出: []
提示:
- 二叉树的节点个数的范围是
[0,100] -100 <= Node.val <= 100
Submission
运行时间: 44 ms
内存: 14.9 MB
# 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: TreeNode) -> List[int]:
if root is None:
return []
result = []
q = deque()
q.append(root)
while q:
size = len(q)
last = None
for i in range(size):
node = q.popleft()
if i == size - 1:
last = node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(last)
return result
Explain
该题解采用广度优先遍历（BFS）的思路。使用一个队列来逐层遍历二叉树，对于每一层，记录该层的最后一个节点，即为从右侧能看到的节点。遍历完所有层后，将记录的最后一个节点的值存入结果数组中。
时间复杂度: O(n)
空间复杂度: O(n)
from collections import deque
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
if root is None:
return []
result = [] # 存储右视图节点的值
q = deque() # 初始化队列
q.append(root) # 根节点入队
while q:
size = len(q) # 当前层的节点数
last = None # 记录当前层的最后一个节点的值
# 遍历当前层的所有节点
for i in range(size):
node = q.popleft() # 出队
if i == size - 1:
last = node.val # 更新最后一个节点的值
# 将非空子节点入队
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(last) # 将当前层的最后一个节点的值加入结果数组
return result
Explore
在BFS算法中，队列按照从左到右的顺序存储每一层的节点。因此，每次从队列中依次取出节点时，最后一个取出的节点自然是该层最右侧的节点。从右侧视图的角度看，这个节点是唯一可见的，因为它没有被任何同层的节点遮挡。所以，记录每层的最后一个节点能确保正确地从右侧视角构建视图。
队列中节点的顺序是由节点入队的顺序决定的，这与它们在二叉树中的位置直接相关。在广度优先遍历时，每个节点的子节点按照从左到右的顺序入队。因此，即使某些节点的值相同，它们在队列中的顺序仍然正确反映了它们在树中作为子节点的结构位置。这确保了节点的处理顺序符合其在树中的实际层级和位置。
在BFS遍历中，只有非空子节点会被加入到队列中。这意味着任何为null的子节点都不会进入队列，因此不会参与到层级遍历中。这种处理方法有效地忽略了null子节点，避免了不必要的空指针操作和错误，同时确保队列中的所有节点都是有效的二叉树节点。这样的处理简化了逻辑并提高了代码的效率和安全性。
题解中的算法逻辑是基于节点存在与否来进行操作，与节点的具体数值（正数、负数或零）无关。因此，无论节点值是什么，算法的处理逻辑和结构不变。只要确保二叉树的构建正确，节点值本身不会影响算法的执行和结果。因此，不需要对特定的节点值范围进行特殊处理。