【LeetCode】在每个树行中找最大值 Java 题解

作者：Albert

2022 年 7 月 03 日
本文字数：1031 字
阅读完需：约 3 分钟

题目描述

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。


示例1：

输入: root = [1,3,2,5,3,null,9]输出: [1,3,9]示例2：
输入: root = [1,2,3]输出: [1,3]
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/find-largest-value-in-each-tree-row著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是二叉树题目。题目要求很明确，需要找出二叉树每一层的最大值。二叉树的题目，常见的解法的深度优先遍历和广度优先遍历。这个题目使用广度优先思路是，按照层遍历，我们才使用队列数据结构，首先将二叉树放入队列中，队列具有先进先出（first in first out）的性质。在队列中，我们如何记录每一层的数据呢？这里需要在每次出队列之前，记录当前队列的长度，然后在循环中出队，保证是在每一层。接下来,我们使用临时变量，动态更新当前层的最大值。具体实现代码如下，供参考。

通过代码

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    public List<Integer> largestValues(TreeNode root) {        List<Integer> ans = new ArrayList<>();        if (root == null) {            return ans;        }        Queue<TreeNode> queue = new LinkedList<>();        queue.offer(root);        while (!queue.isEmpty()) {            int size = queue.size();            int tempMaxVal = Integer.MIN_VALUE;            for (int i = 0; i < size; i++) {                TreeNode temp = queue.poll();                tempMaxVal = Math.max(tempMaxVal, temp.val);                if (temp.left != null) {                    queue.offer(temp.left);                }                if (temp.right != null) {                    queue.offer(temp.right);                }            }            ans.add(tempMaxVal);        }
        return ans;    }}