在每个树行中找最大值

记住「队列按层展开,每层扫一遍取最大」,下面逐帧套它。

什么是层：先找感觉:同一深度的节点属于同一层。根 50 是第 0 层,孩子 30、80 是第 1 层,再往下 60、20、75、40 是第 2 层。我们要在每一层里挑出最大值。

第 0 层就位：进入第 0 层,队列里是 [50]。先把这一整层从左到右扫一遍,边扫边更新「本层最大」。

第 0 层 · 比较：从队首取出 50(红),它是本层第一个节点,先把本层最大记成 50(金色标出)。

第 0 层 · 收孩子：50 看完了。把它的非空孩子 30、80(蓝色)加入下一层,目前下一层攒到了 [30、80]。

第 0 层最大 = 50：第 0 层整层扫完,最大值是 50(金色标出),记进答案。现在各层最大是 [50]。下一层 [30、80] 已就绪,继续。

第 1 层就位：进入第 1 层,队列里是 [30、80]。先把这一整层从左到右扫一遍,边扫边更新「本层最大」。

第 1 层 · 比较：从队首取出 30(红),它是本层第一个节点,先把本层最大记成 30(金色标出)。

第 1 层 · 收孩子：30 看完了。把它的非空孩子 60、20(蓝色)加入下一层,目前下一层攒到了 [60、20]。

第 1 层 · 比较：看节点 80(红):它比当前最大 30 还大,本层最大更新成 80,金色标记移到它身上。

第 1 层 · 收孩子：80 看完了。把它的非空孩子 75、40(蓝色)加入下一层,目前下一层攒到了 [60、20、75、40]。

第 1 层最大 = 80：第 1 层整层扫完,最大值是 80(金色标出),记进答案。现在各层最大是 [50、80]。下一层 [60、20、75、40] 已就绪,继续。

第 2 层就位：进入第 2 层,队列里是 [60、20、75、40]。先把这一整层从左到右扫一遍,边扫边更新「本层最大」。

第 2 层 · 比较：从队首取出 60(红),它是本层第一个节点,先把本层最大记成 60(金色标出)。

第 2 层 · 收孩子：60 是叶子,没有孩子可加,下一层暂时还是 [空]。

第 2 层 · 比较：看节点 20(红):它没有超过当前最大 60,本层最大保持 60 不变。

第 2 层 · 收孩子：20 是叶子,没有孩子可加,下一层暂时还是 [空]。

第 2 层 · 比较：看节点 75(红):它比当前最大 60 还大,本层最大更新成 75,金色标记移到它身上。

第 2 层 · 收孩子：75 是叶子,没有孩子可加,下一层暂时还是 [空]。

第 2 层 · 比较：看节点 40(红):它没有超过当前最大 75,本层最大保持 75 不变。

第 2 层 · 收孩子：40 是叶子,没有孩子可加,下一层暂时还是 [空]。

第 2 层最大 = 75：第 2 层整层扫完,最大值是 75(金色标出),记进答案。现在各层最大是 [50、80、75]。没有下一层了,BFS 即将结束。

完成：每一层的最大值依次是 [50、80、75]。回头看,就是一遍标准的按层 BFS,每层从左到右扫一遍取最大,一次遍历就出全部答案,时间 O(n)。

边界:空树返回空、单节点即自身、负数层靠负无穷起步。

两个追问:DFS 带 depth 也能做;按层 BFS 框架解一大类题。