Leetcode daily question - 515 Find the maximum value in each tree row

1. Title Description

515. Find the maximum in each tree row

Given the root node of a binary tree  root , Please find the maximum value of each layer in the binary tree .

Example 1：

 Input : root = [1,3,2,5,3,null,9]
 Output : [1,3,9]

Example 2：

 Input : root = [1,2,3]
 Output : [1,3]

2. Problem solving ideas and codes

2.1 Their thinking

The topic requires to obtain the maximum value of each layer of the binary tree , Then you can use the sequence traversal of binary tree , Here you can also use the binary tree sequence traversal feature ： When the number of times put in the queue is equal to the length of the queue , Then the next level has been put into the queue . When placing left and right nodes , Calculate the maximum , After each layer is traversed, the maximum value is put into the result list , At the same time, reset the maximum value and put times .

2.2 Code

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);
        int count = 1;
        int max = root.val;
        while (!queue.isEmpty()) {
    
            if (count == queue.size()) {
    
                //  After traversing a layer, put the maximum value of this layer into the result list , And initialize the maximum value and put times 
                ans.add(max);
                max = Integer.MIN_VALUE;
                count = 0;
            }
            TreeNode poll = queue.poll();
            //  When placing left and right nodes , Calculate the maximum 
            if (poll.left != null) {
    
                max = Math.max(max, poll.left.val);
                queue.offer(poll.left);
                count++;
            }
            if (poll.right != null) {
    
                max = Math.max(max, poll.right.val);
                queue.offer(poll.right);
                count++;
            }
        }
        return ans;
    }
}

2.3 test result

Pass the test

3. summary

• Use binary tree sequence traversal
• After each layer is traversed, record the maximum value of this layer