LeetCode 515. 在每个树行中找最大值 · Java 实现题意给定二叉树根节点 root返回每一层节点的最大值组成的列表从上到下。示例1 / \ 3 2 / \ \ 5 3 9输出[1, 3, 9]思路一BFS 层序遍历推荐核心逐层遍历每层用一个变量记录最大值遍历完该层后加入结果。importjava.util.*;classSolution{publicListIntegerlargestValues(TreeNoderoot){ListIntegerresnewArrayList();if(rootnull)returnres;QueueTreeNodequeuenewArrayDeque();queue.offer(root);while(!queue.isEmpty()){intsizequeue.size();intmaxInteger.MIN_VALUE;// 注意初始值不能是 0for(inti0;isize;i){TreeNodenodequeue.poll();maxMath.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{publicListIntegerlargestValues(TreeNoderoot){ListIntegerresnewArrayList();dfs(root,0,res);returnres;}privatevoiddfs(TreeNodenode,intdepth,ListIntegerres){if(nodenull)return;if(depthres.size()){res.add(node.val);// 第一次到达该层直接加入}else{res.set(depth,Math.max(res.get(depth),node.val));}dfs(node.left,depth1,res);dfs(node.right,depth1,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) 会抛 NPEArrayDeque 不允许 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 也能做靠层号 列表长度来第一次占位之后的节点更新该层最大值。