LeetCode 515. 在每个树行中找最大值 · Java 实现
题意
给定二叉树根节点 root，返回每一层节点的最大值组成的列表（从上到下）。
示例：
1 / \ 3 2 / \ \ 5 3 9输出：[1, 3, 9]
思路一：BFS 层序遍历（推荐）
核心：逐层遍历，每层用一个变量记录最大值，遍历完该层后加入结果。
importjava.util.*;classSolution{publicList<Integer>largestValues(TreeNoderoot){List<Integer>res=newArrayList<>();if(root==null)returnres;Queue<TreeNode>queue=newArrayDeque<>();queue.offer(root);while(!queue.isEmpty()){intsize=queue.size();intmax=Integer.MIN_VALUE;// 注意：初始值不能是 0for(inti=0;i<size;i++){TreeNodenode=queue.poll();max=Math.max(max,node.val);if(node.left!=null)queue.offer(node.left);if(node.right!=null)queue.offer(node.right);}res.add(max);}returnres;}}关键点：
· 用 size 锁定当前层节点数，一次循环处理一层。
· max 初始化为 Integer.MIN_VALUE，因为节点值可能为负，不能用 0。
思路二：DFS 记录每层最大值
用 depth 作为层号，res 的下标即层号。第一次到达某层时先占位，之后与当前层最大值比较。
classSolution{publicList<Integer>largestValues(TreeNoderoot){List<Integer>res=newArrayList<>();dfs(root,0,res);returnres;}privatevoiddfs(TreeNodenode,intdepth,List<Integer>res){if(node==null)return;if(depth==res.size()){res.add(node.val);// 第一次到达该层，直接加入}else{res.set(depth,Math.max(res.get(depth),node.val));}dfs(node.left,depth+1,res);dfs(node.right,depth+1,res);}}DFS 的时间也是 O(n)，空间取决于树高 O(h)。和 BFS 相比，代码更短，但"层号 == 列表长度"的判定是重点。
两种方法对比
方法 时间 空间 特点
BFS 层序 O(n) O(w)（最大层宽） 最直观，面试首选
DFS 前序 O(n) O(h)（树高） 代码短，需理解"层号 == 长度"判定
最坏空间都是 O(n)。DFS 在链状树时只占 O(h) = O(n) 的递归栈（比 BFS 的 O(1) 宽还占得多一些），BFS 在满二叉树时占 O(n/2)。实际差异不大。
关键坑点 ⚠️
- max 初始值必须是 Integer.MIN_VALUE，不能是 0
· 节点值可能全是负数，初始化 0 会得到错误的 0。
· 也可用该层第一个节点的值初始化。 - 空树要提前返回空列表
· root == null 时直接 return res;，否则 queue.offer(null) 会抛 NPE（ArrayDeque 不允许 null）。 - 必须用 size 锁定当前层
· while (!queue.isEmpty()) 中每次取 queue.size() 的快照，否则边入队边判断会打乱层级。 - DFS 版本中 depth == res.size() 的判定
· 含义：“第一次到达第 depth 层”。
· 用 depth >= res.size() 也行，但 == 更精确（因为 DFS 深度每次只 +1，不可能跳跃）。 - 别把每层的 max 写进循环外
· max 必须在每层开始时重新初始化，否则会跨层污染。 - ArrayDeque 作为 Queue 用，不支持 offer(null)
· 左右孩子入队前判断 != null。 - 返回值是 List，元素顺序是"从上到下"
· BFS 天然满足；DFS 用层号下标也能保证顺序正确。
一句话总结
BFS 逐层扫，size 定边界，每层取 max（初始 Integer.MIN_VALUE），是本题最标准也最不易错的写法。DFS 也能做，靠"层号 == 列表长度"来第一次占位，之后的节点更新该层最大值。
