LeetCode 199. Binary Tree Right Side View 题解
LeetCode 199. Binary Tree Right Side View 题解
题目描述
给定一个二叉树的根节点root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1：
输入: [1,2,3,null,5,null,4] 输出: [1,3,4]示例 2：
输入: [1,null,3] 输出: [1,3]示例 3：
输入: [] 输出: []解题思路
方法：广度优先搜索（BFS）
思路：
- 使用广度优先搜索遍历二叉树，按层遍历
- 对于每一层，记录最后一个节点的值，即为从右侧能看到的节点
复杂度分析：
- 时间复杂度：O(n)，其中 n 是二叉树的节点个数。每个节点只被访问一次。
- 空间复杂度：O(n)，需要使用队列来进行广度优先搜索。
代码实现
方法：广度优先搜索（BFS）
# 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 [] result = [] queue = deque([root]) while queue: level_size = len(queue) # 遍历当前层的所有节点 for i in range(level_size): node = queue.popleft() # 如果是当前层的最后一个节点，将其值加入结果列表 if i == level_size - 1: result.append(node.val) # 将左子节点加入队列 if node.left: queue.append(node.left) # 将右子节点加入队列 if node.right: queue.append(node.right) return result测试用例
测试用例 1：
输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]
测试用例 2：
输入：root = [1,null,3]
输出：[1,3]
测试用例 3：
输入：root = []
输出：[]
总结
本题是二叉树的经典问题，主要考察对二叉树遍历的理解和应用。通过使用广度优先搜索，我们可以高效地获取二叉树的右视图。
广度优先搜索的核心思想是：按层遍历二叉树，对于每一层，记录最后一个节点的值，即为从右侧能看到的节点。
这种方法不仅适用于二叉树的右视图问题，还可以应用于许多其他需要按层遍历二叉树的场景。掌握广度优先搜索的思想，对于解决这类问题非常重要。