LeetCode(python)199.二叉树的右视图

题目

给定一个二叉树的根节点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 = []

输出：[]

提示:

• 二叉树的节点个数的范围是[0,100]
• -100 <= Node.val <= 100

思路

很自然的一个想法——二叉树的层序遍历，输出每一层的最后一个节点值

在遍历当前层时，用n记录当前层有多少个节点，并判断是否为最后一个节点

代码

# 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 not root: return [] # 二叉树为空 queue = collections.deque() # 定义双端队列 ans = [] # 定义返回的答案 queue.append(root) while queue: # 层序遍历二叉树 n = len(queue) # 记录当前层的节点数 for i in range(n): # 在存进下一层节点时，计数 node = queue.popleft() # 该节点已遍历，弹出 if i == n - 1: # 如果是该层最后一个节点，存入ans ans.append(node.val) if node.left: queue.append(node.left) # 把下一层的节点存进队列 if node.right: queue.append(node.right) return ans