LeetCode_20_FindLargestValueInEachRow

1. question: 在每个树行中找最大值（中等）

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row

示例1：

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

示例2：

输入: root = [1,2,3]
输出: [1,3]

提示：

二叉树的节点个数的范围是 [0,104]
-231 <= Node.val <= 231 - 1

2. answers

这道题比较简单，在层序遍历的基础上，即在遍历每一层的时候，保留最大值即可。代码如下所示：

public class Solution_0018 {

    public static List<Integer> largestValues(TreeNode root) {

        List<Integer> result = new ArrayList<>();

        if(root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        int length, max = root.val;

        queue.offer(root);

        while(!queue.isEmpty()) {

            length = queue.size();
            max = queue.peek().val; // 只取并不弹栈，方便初始化值，与后续的比较。

            while(length > 0) {

                root = queue.poll();
                max = Math.max(max, root.val);

                if(root.left != null) {
                    queue.offer(root.left);
                }

                if(root.right != null) {
                    queue.offer(root.right);
                }

                length --;
            }

            result.add(max);
        }

        return result;
    }

    public static void main(String[] args) {

        TreeNode tn1 = new TreeNode(5);
        TreeNode tn2 = new TreeNode(3);
        TreeNode tn3 = new TreeNode(3, tn1, tn2);

        TreeNode tn4 = new TreeNode(9);
        TreeNode tn5 = new TreeNode(2, null, tn4);

        TreeNode root = new TreeNode(1, tn3, tn5);

        List<Integer> result = largestValues(root);
        for(Integer i: result){
            System.out.println(i);
        }

    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。