Leetcode daily question - 513 Find the value in the lower left corner of the tree

1. Title Description

513. Find the value in the lower left corner of the tree

Given a binary tree The root node root, Please find the of the binary tree   At the bottom   Leftmost   The value of the node .

Suppose there is at least one node in the binary tree .

Example 1:

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

Example 2:

 Input : [1,2,3,4,null,5,6,null,null,7]
 Output : 7

2. Problem solving ideas and codes

2.1 Their thinking

This problem is to get the leftmost node value , In fact, it is the first node on the left of the last layer , So consider using binary tree sequence traversal solution . Here we need to use a feature of sequence traversal ： 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 . Using this feature, when the number of places is equal to the length of the queue , At this point, the first node of this layer is to obtain the queue header from the queue , After traversal, you can get the first node of the last layer . Here, an array is used to simulate a queue .

2.2 Code

class Solution {
    
    public int findBottomLeftValue(TreeNode root) {
    
        int head = 0;
        int tail = 0;
        //  Use arrays to simulate queues 
        TreeNode[] queue = new TreeNode[10000]; 
        queue[tail++] = root;
        int count = 1;
        TreeNode ans = null;
        while (tail - head > 0) {
    
            if (count == tail - head) {
    
                //  If the number of entries equals the number of elements in the queue , be  ans  Equal to header element , And the count is cleared 
                ans = queue[head];
                count = 0;
            }
            //  Pop team leader element 
            TreeNode poll = queue[head++];
            if (poll.left != null) {
    
                queue[tail++] = poll.left;
                count++;
            }
            if (poll.right != null) {
    
                queue[tail++] = poll.right;
                count++;
            }
        }
        return ans.val;
    }
}

2.3 test result

Pass the test

3. summary

• Use binary tree sequence traversal , Get the first node of each layer
• After traversal, you can get the leftmost node of the last layer
• Here, we use arrays to simulate queues. We just want to practice queues , It can also be used. LinkedList To operate