375，在每个树行中找最大值

Original 山大王wld 数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

Don't spend another minute being angry about yesterday.

不要再浪费时间为昨天而懊恼。

问题描述

在二叉树的每一行中找到最大的值。
比如
输入:
1
/ \
3 2
/ \ \
5 3 9

输出: [1, 3, 9]

问题分析：

01BFS求解

关于这道题我们最容易想到的也就是BFS，一层一层遍历，然后在每一层中再找出最大值。前面已经讲过很多BFS的题，这题不是很难。我们来直接看下代码。

 1public List<Integer> largestValues(TreeNode root) {
 2    //LinkedList实现队列
 3    Queue<TreeNode> queue = new LinkedList<>();
 4    List<Integer> values = new ArrayList<>();
 5    if (root != null)
 6        queue.add(root);//入队
 7    while (!queue.isEmpty()) {
 8        int max = Integer.MIN_VALUE;
 9        int levelSize = queue.size();//每一层的数量
10        for (int i = 0; i < levelSize; i++) {
11            TreeNode node = queue.poll();//出队
12            max = Math.max(max, node.val);//记录每层的最大值
13            if (node.left != null)
14                queue.add(node.left);
15            if (node.right != null)
16                queue.add(node.right);
17        }
18        values.add(max);
19    }
20    return values;
21}

02DFS求解

除了一层一层遍历以外，我们还可以使用DFS（深度优先搜索算法）来求解。我们就以上面的举例来画个图分析一下

上面的橙色结点就是遍历的顺序，看明白了上面的图，代码就很容易写出来了，我们再来看下代码

 1public List<Integer> largestValues(TreeNode root) {
 2    List<Integer> res = new ArrayList<>();
 3    helper(root, res, 1);
 4    return res;
 5}
 6
 7//level表示的是第几层，集合res中的第一个数据表示的是
 8// 第一层的最大值，第二个数据表示的是第二层的最大值……
 9private void helper(TreeNode root, List<Integer> res, int level) {
10    if (root == null)
11        return;
12    //如果走到下一层了直接加入到集合中
13    if (level == res.size() + 1) {
14        res.add(root.val);
15    } else {
16        //注意：我们的level是从1开始的，也就是说root
17        // 是第一层，而集合list的下标是从0开始的，
18        // 所以这里level要减1。
19        // Math.max(res.get(level - 1), root.val)表示的
20        // 是遍历到的第level层的root.val值和集合中的第level
21        // 个元素的值哪个大，就要哪个。
22        res.set(level - 1, Math.max(res.get(level - 1), root.val));
23    }
24    //下面两行是DFS的核心代码
25    helper(root.left, res, level + 1);
26    helper(root.right, res, level + 1);
27}