Depth First Search, DFS Breath First Search leetcode

  • DFS BFS

V

A tree is a special case of a graph (a connected acyclic graph is a tree). Next, let's take a look at how to traverse the tree using depth-first traversal.

1. We start traversing from the root node 1, and its adjacent nodes are 2, 3, 4. First traverse node 2, then traverse the child node 5 of 2, and then traverse the child node 9 of 5.

2. A road in the above figure has been reached to the end (9 is a leaf node, and there are no more traversable nodes). At this time, go back to the previous node 5 from 9 to see if there are any nodes other than 9 in node 5 , Does not continue to fall back to 2, and 2 does not have nodes other than 5, and falls back to 1, 1 has node 3 other than 2, so depth-first traversal starts from node 3, as follows

3. In the same way, starting from 10 and going back to 6, 6 has no child nodes other than 10, and then going back up, it is found that 3 has a child 7 other than 6, so it will traverse 7 at this time

3. Go back from 7 to 3 and 1, and find that 1 and node 4 have not been traversed, so at this time, traverse along 4 and 8, so that the traversal is completed

The traversal sequence of the complete node is as follows (the blue number on the node represents)

I believe everyone can see that the above traversal is not difficult to find that this is the pre-order traversal of the tree. In fact, whether it is a pre-order traversal, a middle-order traversal, or a post-order traversal, it is a depth-first traversal.

So how to implement depth-first traversal? There are two manifestations of recursion and non-recursion. Next, let's take a binary tree as an example to see how to implement depth-first traversal with recursion and non-recursion respectively.

1. Recursive implementation

The recursive implementation is relatively simple. Because it is a pre-order traversal, we can traverse the current node, the left node, and the right node in turn. For the left and right nodes, it is enough to traverse their left and right nodes in turn, and then continue to recurse until the leaf node (Recursive termination condition), the code is as follows

public class Solution { private static class Node { /** * Node value */ public int value; /** * Left node */ public Node left; /** * Right node */ public Node right; public Node ( int value, Node left, Node right) { this .value = value; this .left = left; this .right = right; } } public static void dfs (Node treeNode) { if (treeNode == null ) { return ; } //Traverse the nodes process(treeNode) //Traverse the left node dfs(treeNode.left); //Traverse the right node dfs(treeNode.right); } } Copy code

Recursion is very expressive and easy to understand, but if the hierarchy is too deep, it is easy to cause stack overflow. So let s focus on the non-recursive implementation

2. Non-recursive implementation

Carefully observe the characteristics of depth-first traversal. For binary trees, since it is a first-order traversal (first traverse the current node, then traverse the left node, then traverse the right node), we have the following ideas

  1. For each node, first traverse the current node, then push the right node onto the stack, and then push the left node (so when the stack is popped, the left node will be traversed first, which meets the depth-first traversal requirements)
  2. Pop the stack and get the node at the top of the stack. If the node is not empty, repeat step 1. If it is empty, end the traversal.

Let's take the following binary tree as an example to see how to use the stack to implement DFS.

The overall animation is as follows

The overall idea is still relatively clear. Use the stack to push the node to be traversed on the stack, and then check whether there are untraversed nodes on this node after popping the stack. , It is not difficult to write the following binary tree depth-first traversal code implemented with stack:

/** * Use stack to implement dfs * @param root */ public static void dfsWithStack (Node root) { if (root == null ) { return ; } Stack<Node> stack = new Stack<>(); //first push the root node onto the stack stack.push(root); while (!stack.isEmpty()) { Node treeNode = stack.pop(); //Traverse the nodes process(treeNode) //First press the right node if (treeNode.right != null ) { stack.push(treeNode.right); } //Press the left node again if (treeNode.left != null ) { stack.push(treeNode.left); } } } Copy code

It can be seen that using the stack to implement depth-first traversal is actually not complicated, and there is no need to worry about stack overflow problems caused by excessively deep levels such as recursion.

Breadth first traversal

Breadth-first traversal refers to starting from an untraversed node in the graph, first traversing the neighboring nodes of this node, and then traversing the neighboring nodes of each neighboring node in order.

The breadth-first traversal graph of the tree described above is as follows, the value of each node is their traversal order. So breadth-first traversal is also called layer sequence traversal, first traverse the first layer (node 1), then traverse the second layer (nodes 2, 3, 4), the third layer (5, 6, 7, 8), the fourth layer (9, 10).

Depth-first traversal uses stacks, while breadth-first traversal uses queues. Let s take a binary tree as an example to see how to use queues for depth-first traversal.

The animation is as follows

I believe that after reading the above animation, it is not difficult to write the following code

/** * Use queues to implement bfs * @param root */ private static void bfs (Node root) { if (root == null ) { return ; } Queue<Node> stack = new LinkedList<>(); stack.add(root); while (!stack.isEmpty()) { Node node = stack.poll(); System.out.println( "value = " + node.value); Node left = node.left; if (left != null ) { stack.add(left); } Node right = node.right; if (right != null ) { stack.add(right); } } } Copy code

Exercises

Next, let's take a look at some of the problems that use DFS and BFS to solve problems in Leetcode:

Leetcode 104, 111: Given a binary tree, find out its maximum/minimum depth.

For example:
Given a binary tree [3,9,20,null,null,15,7],

3 // 9 20 // 15 7 Copy code

Then its minimum depth is 2 and its maximum depth is 3

Problem-solving idea: This problem is relatively simple. It is just a variation of depth-first traversal. You only need to recursively find the maximum/minimum depth of the left and right subtrees. How to find the depth? Every time the function is called recursively, the depth increases by one. It is not difficult to write the following code

/** * leetcode 104: Find the maximum depth of the tree * @param node * @return */ public static int getMaxDepth (Node node) { if (node == null ) { return 0 ; } int leftDepth = getMaxDepth(node.left) + 1 ; int rightDepth = getMaxDepth(node.right) + 1 ; return Math.max(leftDepth, rightDepth); } /** * leetcode 111: Find the minimum depth of the tree * @param node * @return */ public static int getMinDepth (Node node) { if (node == null ) { return 0 ;} if (node.left == null ) { return 1 + getMinDepth(node.right);} if (node .right == null ) { return 1 + getMinDepth(node.left);} int leftDepth = getMinDepth(node.left); int rightDepth = getMinDepth(node.right); return 1 + Math.min(leftDepth, rightDepth); } Copy code

leetcode 102: Give you a binary tree, please return the node value obtained by traversing it in layer order. (That is, visit all nodes layer by layer, from left to right).
Example, given a binary tree: [3,9,20,null,null,15,7]

3 // 9 20 // 15 7 Copy code

Return the result of its level traversal:

[ [3], [9,20], [15,7] ] Copy code

Problem-solving idea: Obviously this problem is a variant of breadth-first traversal. You only need to add the nodes of each layer to the same array in the process of breadth-first traversal. The key to the problem is to traverse the same layer of nodes. , You must first calculate the number of nodes in the same layer. Otherwise, because BFS is implemented using queues, the left and right child nodes will be enqueued during the traversal process. If the nodes of the same layer are not calculated in advance, the left and right nodes of the same layer will also be added. Remember to add to the nodes of the same layer! The animation is as follows

According to the above animation ideas, it is not difficult to get the code as follows:

Java code

/** * leetcdoe 102: Binary tree traversal, using bfs * @param root */ private static List<List<Integer>> bfsWithBinaryTreeLevelOrderTraversal(Node root) { if (root == null ) { //The root node is empty, indicating that the binary tree does not exist, directly return an empty array return Arrays.asList(); } //The final layer sequence traversal result List<List<Integer>> result = new ArrayList<>(); Queue<Node> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { //Record each layer List<Integer> level = new ArrayList<>(); int levelNum = queue.size(); //Traverse the nodes of the current layer for ( int i = 0 ; i <levelNum; i++) { Node node = queue.poll(); //The left and right children of the first node of the team join the team. Since the levelNum is calculated before joining the team, the left and right nodes of the team will not be traversed to the current layer if (node.left != null ) { queue.add(node.left); } if (node.right != null ) { queue.add(node.right); } level.add(node.value); } result.add(level); } return result; } Copy code

Python code:

class Solution : def levelOrder ( self, root ): """ :type root: TreeNode :rtype: List[List[int]] """ res = [] #Nested list, save the final result if root is None : return res from collections import deque que = deque([root]) #Queue, save the node to be processed while len (que)!= 0 : lev = [] #List , save the value of the node at this level thislevel = len (que) #The number of nodes at this level while thislevel!= 0 : head = que.popleft() # Popup Team First Node # The left and right children of the first node of the team join the team if head.left is not None : que.append(head.left) if head.right is not None : que.append(head.right) lev.append(head.val) #The value of the first node of the team is pressed into this level thislevel-= 1 res.append(lev) return resCopy code

It is obvious to use BFS for this question, but in fact, DFS can also be used. If DFS can be used in the interview, it will be a relatively big bright spot.

How to deal with DFS, we know that DFS can be implemented by recursion, in fact, as long as a "layer" variable is added to the recursive function, as long as the node belongs to this layer, the node is put into the array of the corresponding layer Here, the code is as follows:

private static final List<List<Integer>> TRAVERSAL_LIST = new ArrayList<>(); /** * leetcdoe 102: Binary tree traversal, using dfs * @param root * @return */ private static void dfs (Node root, int level) { if (root == null ) { return ; } if (TRAVERSAL_LIST.size() <level + 1 ) { TRAVERSAL_LIST.add( new ArrayList<>()); } List<Integer> levelList = TRAVERSAL_LIST.get(level); levelList.add(root.value); //Traverse the left node dfs(root.left, level + 1 ); //Traverse the right node dfs(root.right, level + 1 ); } Copy code

DFS, the application of BFS in search engines

We use search engines like Google and Baidu almost every day. Do you know how these search engines work? Simply put, there are three steps

1. Web crawling

The search engine crawls the web page through the crawler, and obtains the HTML code of the page and stores it in the database

2. Pretreatment

The index program performs text extraction, Chinese word segmentation, (inverted) indexing and other processing on the crawled page data for use by the ranking program

3. Ranking

After the user enters the keyword, the ranking program calls the index database data to calculate the correlation, and then generates a search result page in a certain format.

Let's focus on the first step, web crawling.

The general operation of this step is as follows: Assign a set of starting web pages to the crawler. We know that the web page actually contains many hyperlinks. After the crawler crawls a web page, it parses and extracts all the hyperlinks in the web page, and then crawls them in turn. Take out these hyperlinks, and then extract the web page hyperlinks. . . , So that continuous repetition can continue to extract web pages based on hyperlinks. As shown below

As shown above, a picture is finally formed, so the question is transformed into how to traverse this picture. Obviously, it can be traversed in a depth-first or breadth-first manner.

If it is breadth-first traversal, first crawl the first page of the first layer in turn, and then crawl the hyperlinks in each page in turn. If it is depth-first traversal, crawl the start page 1 first, and then crawl this page Link..., after crawling, crawl the starting page 2...

In fact, crawlers are used together with depth-first and breadth-first strategies. For example, in the initial webpage, some webpages are more important (higher weight), then depth-first traversal of this webpage is performed, and then the others are traversed. (The weight is the same) The starting webpage is traversed by breadth first.

summary

DFS and BFS are two very important algorithms. You must master them. In order to facilitate the explanation, this article only does DFS and BFS for trees. You can try how to write code if you use pictures. The principle is actually the same, but Graphs and trees have different representations. DFS generally solves connectivity problems, while BFS generally solves shortest path problems. Later, when we have the opportunity, we will learn and find together, Dijkstra, Prism algorithm, etc., so stay tuned !