LeetCode 题解工作台
在每个树行中找最大值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。 示例1： 输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9] 示例2： 输入: root = [1,2,3] 输出: [1,3] 提示： 二叉树的节点个数的范围是 [0,10 4 ] -2 31 3…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们定义一个队列 ，将根节点放入队列中。每次从队列中取出当前层的所有节点，找出最大值，然后将下一层的所有节点放入队列中，直到队列为空。 时间复杂度 ，空间复杂度 。其中 是二叉树的节点个数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1：
输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9]
示例2：
输入: root = [1,2,3] 输出: [1,3]
提示：
- 二叉树的节点个数的范围是
[0,104] -231 <= Node.val <= 231 - 1
解题思路
方法一：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
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
ans = []
if root is None:
return ans
q = deque([root])
while q:
x = -inf
for _ in range(len(q)):
node = q.popleft()
x = max(x, node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(x)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(h) |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates familiarity with tree traversal techniques like DFS and BFS.
- question_mark
The candidate tracks row-wise maximum values accurately.
- question_mark
The candidate optimizes space usage during the tree traversal.
常见陷阱
外企场景- error
Not handling edge cases, like empty trees or trees with only one node.
- error
Confusing the traversal order, leading to incorrect row-wise maximums.
- error
Failing to update the maximum value correctly across all rows.
进阶变体
外企场景- arrow_right_alt
Finding the second largest value in each row.
- arrow_right_alt
Handling trees that contain non-unique values within a row.
- arrow_right_alt
Optimizing for memory usage in sparse trees.