题目内容
![[LC515]在每个树的行中找最大值](https://johngo-pic.oss-cn-beijing.aliyuncs.com/articles/20230605/2913076-20220624223003700-1848585637.png)
![[LC515]在每个树的行中找最大值](https://www.johngo689.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
题目分析
这是一道典型的树结构遍历题，可以使用层序遍历(BFS)或者(DFS)进行解题。
- 在BFS中，使用队列结构遍历树的每一层并维护每层的最大值。
- 在DFS中，由于并不是一层一层的去访问树的节点，因此需要使用HashMap来维护每个层最大值。
BFS
public List<integer> largestValues(TreeNode root) {
Deque<treenode> queue = new ArrayDeque();
if (root != null) queue.add(root);
List<integer> res = new ArrayList();
while(!queue.isEmpty()){
int sz = queue.size();
Integer levelMax = Integer.MIN_VALUE;
for(int i = 0; i < sz; i++){
TreeNode node = queue.pollFirst();
levelMax = Math.max(levelMax, node.val);
if (node.left != null) queue.addLast(node.left);
if (node.right != null) queue.addLast(node.right);
}
res.add(levelMax);
}
return res;
}
</integer></treenode></integer>
DFS
int maxDepth = 0;
Map<integer, integer> map = new HashMap<>();
public List<integer> largestValues(TreeNode root) {
List<integer> res = new ArrayList<>();
dfs(root, 1);
for (int i = 1; i <= max; i++) res.add(map.get(i)); return res; } void dfs(treenode node, int depth) { if (node="=" null) ; maxdepth="Math.max(maxDepth," depth); map.put(depth, math.max(map.getordefault(depth, integer.min_value), node.val)); dfs(node.left, depth + 1); dfs(node.right, < code></=></integer></integer></integer,>
Original: https://www.cnblogs.com/xy1997/p/16410447.html
Author: xingyuanyuan
Title: [LC515]在每个树的行中找最大值
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/588104/
转载文章受原作者版权保护。转载请注明原作者出处！