算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试 算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 在每个树行中找最大值，我们先来看题面：
https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/
Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例
解题
https://blog.csdn.net/qq_35655602/article/details/109520323
方法一：BFS（按照层序遍历的思想，进行广度优先遍历）
class Solution {
public List<Integer> largestValues(TreeNode root) {
//LinkedList实现队列
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> values = new ArrayList<>();
if (root != null)
queue.add(root);//入队
while (!queue.isEmpty()) {
int max = Integer.MIN_VALUE;
int levelSize = queue.size();//每一层的数量
for (int i = 0; i < levelSize; i ) {
TreeNode node = queue.poll();//出队
max = Math.max(max, node.val);//记录每层的最大值
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
values.add(max);
}
return values;
}
}方法二：DFS
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> res = new ArrayList<>();
helper(root, res, 1);
return res;
}
//level表示的是第几层，集合res中的第一个数据表示的是
// 第一层的最大值，第二个数据表示的是第二层的最大值……
private void helper(TreeNode root, List<Integer> res, int level) {
if (root == null)
return;
//如果走到下一层了直接加入到集合中
if (level == res.size() 1) {
res.add(root.val);
} else {
//注意：我们的level是从1开始的，也就是说root
// 是第一层，而集合list的下标是从0开始的，
// 所以这里level要减1。
// Math.max(res.get(level - 1), root.val)表示的
// 是遍历到的第level层的root.val值和集合中的第level
// 个元素的值哪个大，就要哪个。
res.set(level - 1, Math.max(res.get(level - 1), root.val));
}
//下面两行是DFS的核心代码
helper(root.left, res, level 1);
helper(root.right, res, level 1);
}
}好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
上期推文：
LeetCode1-500题汇总，希望对你有点帮助！
LeetCode刷题实战501：二叉搜索树中的众数
LeetCode刷题实战502：IPO
LeetCode刷题实战503：下一个更大元素 II
LeetCode刷题实战504：七进制数
LeetCode刷题实战505：迷宫II
LeetCode刷题实战506：相对名次
LeetCode刷题实战507：完美数
LeetCode刷题实战508：出现次数最多的子树元素和
LeetCode刷题实战509：斐波那契数
LeetCode刷题实战510：二叉搜索树中的中序后继 II
LeetCode刷题实战511：游戏玩法分析 I
LeetCode刷题实战512：游戏玩法分析 II
LeetCode刷题实战513：找树左下角的值
