好的，我为你随机选择一个尚未讲过的搜索算法题目。

题目描述：LeetCode 515. 在每个树行中找最大值

给你一棵二叉树的根节点 root，请你找出该二叉树中每一层的最大值，并以数组形式返回。

示例 1:
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:
1
/
3 2
/ \
5 3 9
第0层最大值是 1
第1层最大值是 3
第2层最大值是 9

示例 2:
输入: root = [1,2,3]
输出: [1,3]

解题过程循序渐进讲解

这是一个典型的树形结构层序遍历问题，核心是在遍历过程中区分不同层级，并记录每层的最大值。我们通常使用广度优先搜索算法来解决。

第1步：理解问题与数据结构

• 题目输入是一棵二叉树的根节点。每个节点包含一个整数值。
• 我们需要按层级来处理节点，而非深度优先。这意味着我们需要一种能“一层一层”访问节点的方法。
• 最终输出是一个列表，列表的第 i 个元素对应二叉树第 i 层的最大值。

第2步：选择核心算法——广度优先搜索

• 广度优先搜索天然地按照层级顺序遍历节点。我们从根节点开始，先访问所有第0层节点（即根节点本身），然后是第1层，接着第2层，以此类推。
• BFS通常借助一个队列来实现。队列的特点是“先进先出”，这保证了我们总是先处理完同一层的节点，再处理下一层的节点。

第3步：构思解题步骤

1. 初始化：如果根节点为空，直接返回空列表。创建一个队列（通常用 deque），将根节点放入队列。同时，创建一个空列表 result 用于存放结果。
2. 开始层级遍历：只要队列不为空，就说明还有节点未处理。
   a. 确定当前层级的节点数：在开始处理新一层之前，先记录当前队列的长度 level_size。这个长度就是当前这一层所有节点的数量。
   b. 初始化当前层最大值：因为节点值可能为负数，所以我们初始化为一个非常小的数（如 -float('inf') 或 INT_MIN）。
   c. 处理当前层所有节点：循环 level_size 次。
   - 从队列左侧弹出节点。
   - 用该节点的值更新当前层最大值。
   - 如果该节点有左子节点，将左子节点加入队列右侧。
   - 如果该节点有右子节点，将右子节点加入队列右侧。
   d. 记录结果：将当前层最大值添加到 result 列表的末尾。
3. 返回结果：当队列为空，所有层级处理完毕，返回 result 列表。

第4步：逐步演算（以示例1为例）
初始状态：
队列 = [1], result = []

第0层遍历：

• 当前队列长度 level_size = 1。
• 初始化 level_max = -∞。
• 循环1次：
  • 弹出节点 1， level_max = max(-∞, 1) = 1。
  • 将节点 1 的左子节点 3、右子节点 2 依次加入队列。队列 = [3, 2]。
• 将 level_max (1) 加入 result。result = [1]。

第1层遍历：

• 当前队列长度 level_size = 2。
• 初始化 level_max = -∞。
• 循环2次：
  1. 弹出节点 3， level_max = max(-∞, 3) = 3。将其子节点 5, 3 入队。队列 = [2, 5, 3]。
  2. 弹出节点 2， level_max = max(3, 2) = 3。将其子节点 9 入队。队列 = [5, 3, 9]。
• 将 level_max (3) 加入 result。result = [1, 3]。

第2层遍历：

• 当前队列长度 level_size = 3。
• 初始化 level_max = -∞。
• 循环3次：
  1. 弹出节点 5， level_max = max(-∞, 5) = 5。它没有子节点。
  2. 弹出节点 3， level_max = max(5, 3) = 5。
  3. 弹出节点 9， level_max = max(5, 9) = 9。
• 将 level_max (9) 加入 result。result = [1, 3, 9]。

队列为空，遍历结束。返回 [1, 3, 9]。

第5步：代码实现要点（Python示例）

from collections import deque
from typing import Optional, List

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]:
        if not root:
            return []
        
        result = []
        queue = deque([root])  # 初始化队列，加入根节点
        
        while queue:
            level_size = len(queue)  # 关键：提前记录当前层节点数
            level_max = float('-inf')  # 初始化当前层最大值
            
            for _ in range(level_size):
                node = queue.popleft()  # 弹出当前层的一个节点
                level_max = max(level_max, node.val)  # 更新最大值
                
                # 将下一层的子节点加入队列
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                    
            result.append(level_max)  # 保存当前层结果
        
        return result

关键点总结：

1. 层级分离的关键：在每一轮 while 循环开始时，使用 level_size = len(queue) 记录当前层的节点数量，然后通过一个固定次数的 for 循环来处理完正好这一层的所有节点。这样，当 for 循环结束时，队列里剩下的就全是下一层的节点了。
2. 初始化最大值：使用 float(‘-inf’) 确保任何有效的节点值都能将其更新。
3. 时间复杂度：O(N)，其中 N 是二叉树的节点数，每个节点恰好被访问一次。
4. 空间复杂度：O(W)，其中 W 是二叉树的最大宽度（即最宽那一层的节点数），在最坏情况下（完美二叉树），队列中最多会存储约 N/2 个节点。