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, val0, leftNone, rightNone): # 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 []输出[]总结本题是二叉树的经典问题主要考察对二叉树遍历的理解和应用。通过使用广度优先搜索我们可以高效地获取二叉树的右视图。广度优先搜索的核心思想是按层遍历二叉树对于每一层记录最后一个节点的值即为从右侧能看到的节点。这种方法不仅适用于二叉树的右视图问题还可以应用于许多其他需要按层遍历二叉树的场景。掌握广度优先搜索的思想对于解决这类问题非常重要。