Shulou(Shulou.com)06/01 Report--

Editor to share with you the breadth-first search algorithm in LeetCode example analysis, I believe that most people do not know much about it, so share this article for your reference, I hope you will learn a lot after reading this article, let's go to know it!

First, recognize the breadth-first search algorithm

Breadth-first search (BFS) algorithm is a traversal method of a graph. Its core idea is to start from a certain node of the graph, traverse the neighboring nodes in turn, and then continue to traverse from these neighboring nodes to the outer nodes until all the nodes of the connected graph are accessed.

As shown in the figure above, six nodes A, B, C, D, E and F form a connected graph. We use the breadth-first search algorithm to traverse the connected graph. Starting from point A, we find the adjacent nodes of point A, point B and point F, and then find the adjacent nodes of point B and point F, point C and point E, respectively. Finally, we find the common adjacent node D of point C and point E. So the traversal result we get is ABFCED.

Second, Leetcode common breadth-first search form

When we open the breadth-first search tab of Leetcode and look at the relevant algorithm questions, we will find that many of the questions simplify the connected graph to be displayed in the form of tree or binary tree. Therefore, we can analyze the breadth-first search algorithm from the perspective of tree / binary tree. As long as we understand the breadth-first search of the tree, the breadth-first search of the graph is just the difference in the selection of neighboring nodes.

The breadth-first search algorithm is simplified to a hierarchical traversal algorithm in the tree / binary tree, that is, starting from the root node of the tree, traversing the children of the root node in turn, and then using these children as the root node to cycle through the above operations. until all the nodes are traversed.

As shown in the following figure, the hierarchical traversal of the tree is a special breadth-first search. According to the traversal rules above, it is not difficult to find that the breadth-first search sequence of the tree is ABCDEFG.

Third, an algorithm problem to explain the specific implementation of BFS.

I selected a typical breadth-first search algorithm on Leetcode to sort out the basic implementation of BFS algorithm. The topics are as follows:

Idea: from the meaning of the question, it is not difficult to see that the core problem of this problem is to find out the value of the rightmost node in each layer of the binary tree and put it into the array and return it to the array. Obviously, the rightmost node of each layer can be easily found by using the breadth-first search algorithm.

For the breadth-first search algorithm, we need to apply for an auxiliary queue to help us store each node at each layer. First of all, the root node needs to be null, if the root node is empty, it will directly return an empty array, otherwise the root node will be stored in the queue. Next, we need to take out all the nodes in this layer of the queue and find out their child nodes and put them in the queue. It is important to note that when you get to the rightmost node, you should store the value of that node in the array. Loop the process until you traverse all the nodes of the binary tree to get the final result.

Class Solution {

Public List rightSideView (TreeNode root) {

List ans = new ArrayList ()

If (root = = null) {

Return ans

}

Queue queue = new LinkedList ()

Queue.add (root)

While (! queue.isEmpty ()) {

Int count = queue.size ()

TreeNode currentNode = null

While (count > 0) {

Count--

CurrentNode = queue.poll ()

If (currentNode.left! = null) {

Queue.add (currentNode.left)

}

If (currentNode.right! = null) {

Queue.add (currentNode.right)

}

}

Ans.add (currentNode.val)

}

Return ans

}

}

Algorithm complexity analysis: the algorithm needs to access each node in the binary tree and the access time of each node is O (1), so the final event complexity is O (n). For space complexity, we apply for an auxiliary queue to help store binary tree nodes, and the final space complexity can also be expressed as O (n).

The above is all the contents of the article "sample Analysis of breadth-first search algorithm in LeetCode". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.