preface

Is the HXDM asleep? I can’t sleep! Just into the community security let me show health code, I was in a daze opened the alipay fund, and then the security let me in!

The roof is cold! It was a bit chilly tonight, I looked at the queue in front of a little too many people, so I wrote a solution, give a thumbs up 😭😭😭

Topic describes

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

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:

Input: 2 / \ 1 3 Output: 1Copy the code

Example 2:

Input: 1 / \ 2 3 / / \ 4 5 6/7 Output: 7Copy the code

Note: You can assume that the tree (that is, the given root node) is not NULL.

Their thinking

Given a binary tree root, find the leftmost value on the last row of the tree.

See this kind of binary tree for a value of the topic, for our foundation is relatively weak development, do not think up is a step in place, think how to write the kind of solution.

We can start from the simplest way to understand, first to do the problem, don’t be afraid to write too simple. So we can do this with BFS traversal.

Let’s take a look at BFS and DFS.

BFS: embosses-first-search, width (Breadth) priority; DFS: depth-first search. Both are a way of searching or traversing a graph or tree, but in different forms. For a graph, the search is to start at a certain point, keep searching for all the points connected to it, and then continue until all the points have been searched.

The above is only a brief introduction, the introduction of more detailed can be seen in this article BFS & DFS

We normally iterate from top to bottom and left to right, but notice that we’re looking for the bottom left corner of the tree, so we’re looking for the bottom left corner of the tree!

First we define an array queue = [] and res = 0 for recording.

We then add the given binary tree root to the queue array and iterate over it.

Queue. Shift () is the value of the current node, which is then recorded in res.

In order from right to left, we first determine the right of the current node and add it to the array queue.

Then determine the left of the current node and add it to the array queue.

By the end of the loop, this element must be the leftmost value of the tree!

At this time interested can continue to study how to optimize!

The problem solving code

var findBottomLeftValue = function(root) {
    let queue = [];
    let res = 0;
    queue.push(root);
    while(queue.length) {
        const node = queue.shift();
        res = node.val;
        if (node.right) {
            queue.push(node.right);
        }
        if (node.left) {
            queue.push(node.left);
        }
    }
    return res;
};
Copy the code

Swipe questions and punch out records

Here is the previous swipe card records, you can have a look, if you have any different views and views or feel what is wrong, welcome to leave a message in the comment area! 🙏 🙏 🙏

[LeetCode0303 topic area and retrieval – array immutable] | punch brush

[LeetCode1200. Minimum absolute difference] | punch brush

[LeetCode0304 topic 2 d area and retrieval – matrix immutable] | punch brush

[LeetCode11 topic containers of most water] | punch brush

[LeetCode0338 topic bit count] | punch brush

[LeetCode209 topic length minimum subarray] | punch brush

[LeetCode236 topic in recent common ancestor of binary tree] | punch brush

[LeetCode141 topic circular linked list] | punch brush

[LeetCode53 topic most architectural sequence and] | punch brush

[LeetCode48 topic rotating images] | punch brush

[LeetCode155 topic minimum stack] | punch brush

[LeetCode1124 problem well, the longest period of a] | punch brush

[LeetCode274 problem H index] | punch brush

[LeetCode367 problem effective completely square number] | punch brush

[LeetCode1047 problem delete all adjacent duplicates of the string] | punch brush

[LeetCode160 topic cross linked list] | punch brush

[LeetCode1438 topic absolute difference does not exceed the limit of the longest continuous subarray] | punch brush

[LeetCode434 problem the number of words in a string] | punch brush

[LeetCode75 topic classification of color] | punch brush

conclusion

Come on! HXDM!!!!!! 💪 💪 💪

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign