515. 在每个树行中找最大值(中)
发布时间 2023-12-23 13:55:17作者: Frommoon
题目
- 给定一棵二叉树的根节点 root ,请找出该二叉树中每一层的最大值。
题解:BFS
- BFS遍历每一层,在每一层每一个元素出队的时候更新最大值,保存每一层的最大值,最后返回即可。
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
if not root:# 如果根节点为空,返回空列表
return []
q=[root]#用列表做队列
res=[] # 存储每层的最大值
while q:
size=len(q)
max_val=float('-inf')# 当前层的最大值初始化为负无穷小
for _ in range (size):
cur=q.pop(0)# 从队列中取出当前节点
max_val=max(max_val,cur.val)# 更新当前层的最大值
if cur.left:
q.append(cur.left)# 将左子节点添加到队列中
if cur.right:
q.append(cur.right) # 将右子节点添加到队列中
res.append(max_val) # 将当前层的最大值添加到结果列表中
return res # 返回每层的最大值列表