Give it a like and take a look. Good habit! In this paper, making github.com/OUYANGSIHAI… It has been included. This is the summary of Java interview for first-line big factory that I spent 3 months to summarize. I have received the offer from big factory. In addition, the original articles are first published on my personal blog: blog.ouyangsihai.cn, welcome to visit.
Today, let’s talk about the solution methods of DFS. These methods are summarized after the experience, which is worth learning from.
1 Look at DFS from binary tree
The thought of the binary tree is actually very simple, we just begin to learn binary tree, when doing the binary tree traversal is the most common method is recursive traversal, in fact, you will find that the topic of binary tree of problem solving methods are basically recursion problem solving, we only need to walk the one step, the other by recursion.
Let’s first look at the recursive versions of pre-order, mid-order, and post-order traversal of a binary tree.
// preorder traversal
void traverse(TreeNode root) {
System.out.println(root.val);
traverse(root.left);
traverse(root.right);
}
// middle order traversal
void traverse(TreeNode root) {
traverse(root.left);
System.out.println(root.val);
traverse(root.right);
}
// subsequent traversal
void traverse(TreeNode root) {
traverse(root.left);
traverse(root.right);
System.out.println(root.val);
}
Copy the codeAnd what you’ll see is that when you walk through a binary tree, you’ll see that the overall framework for walking through a binary tree, and this is actually the overall framework for solving a binary tree, is something like this.
void traverse(TreeNode root) {
// Here we change the output to some other operation, we only do the first step, the rest is done recursively.
traverse(root.left);
traverse(root.right);
}
Copy the codeWhen we solve the problem, we just need to think about how the current operation should be implemented, and how to implement the following recursion, and whether to use the front-in-order or back-order traversal, depending on the specific situation.
So let’s do a couple of warm-up problems with binary trees, just to get a feel for this approach.
In addition, the words of these knowledge, I have written the original article, more systematic explanation, we can have a look, there will be certain harvest.
| The serial number | original |
|---|---|
| 1 | 【 Original 】 Distributed architecture series articles |
| 2 | Activiti workflow tutorial |
| 3 | In-depth understanding of the Java Virtual Machine tutorial |
| 4 | Java8 tutorial |
| 5 | MySQL art World |
1. How do I add one to all the nodes in a binary tree
So first of all, again, let’s write the framework.
void traverse(TreeNode root) {
// Here we change the output to some other operation, we only do the first step, the rest is done recursively.
traverse(root.left);
traverse(root.right);
}
Copy the codeNext, consider what the current step requires, in this case, of course, to add one to the current node.
void traverse(TreeNode root) {
if(root == null) {
return;
}
// Add one to the current node instead.
root.val += 1;
traverse(root.left);
traverse(root.right);
}
Copy the codeDid it just happen?
Not great? Let’s do another simple one.
2. How to determine whether two binary trees are the same binary tree
So let’s just think about what we need to do in the next step, which is what happens, this is the same binary tree?
1) The current node of both trees is null: root1 == null && root2 == null 2) two trees any one of the current node is empty: root1 = = null | | root2 = = null, at this time, of course, is false. Root1.val! = root1.val! = root1.val! = root2.val, returns false.
So the answer is obvious.
boolean isSameTree(TreeNode root1, TreeNode root2) {
// If both are empty
if (root1 == null && root2 == null) return true;
// One is null and one is non-null
if (root1 == null || root2 == null) return false;
// Both are not empty, but val is different
if(root1.val ! = root2.val)return false;
// do it recursively
return isSameTree(root1.left, root2.left) && isSameTree(root1.right, root2.right);
}
Copy the codeWith the above explanation, I believe you have a basic idea, let’s try some difficult topics, small test knife.
3. Leetcode is moderately difficult to parse
114. Binary tree expands to a linked list
This problem is medium difficulty in binary tree, but the pass rate is very low, so let’s use the above ideas to see if we can easily solve this problem.
This topic at first glance, according to the front of the train of thought, you can first choose the way to solve the preorder traversal, yes, but, more troublesome, because of the way preorder traversal will change right node point, lead to more troublesome, so, if not preorder traversal, consider the order and the order of traversal, because, at the time of expansion, We just need to change the direction of the left and right nodes, so actually, the best way to do this is to use follow-up traversal, since it is follow-up traversal, so we can quickly write out the framework of follow-up traversal.
public void flatten(TreeNode root) {
if(root == null) {return;
}
flatten(root.left);
flatten(root.right);
// Consider what to do next
}
Copy the codeSo that gives us the basic idea of the problem, and then we just have to think about what we need to do in the current step to solve the problem.
Current step: because it is after the sequence traversal, so order is monitored, we can see that from an order apparently left nodes connected by first connecting node right after, so, we must first save right node values, then connect the nodes on the left, at the same time, we expand, the only right nodes, so the left node should be set to null.
After analysis, the code can be written directly.
public void flatten(TreeNode root) {
if(root == null) {return;
}
flatten(root.left);
flatten(root.right);
// Consider what to do next
TreeNode temp = root.right;//
root.right = root.left;// The right pointer refers to the left node
root.left = null;// The left node value is null
while(root.right ! =null){
root = root.right;
}
root.right = temp;// Attach the right node to the right pointer
}
Copy the codeSo that’s the answer, it’s not the best answer, but it’s probably the best way to think about problems like binary trees, and it’s a good way to think about the idea of DFS.
105. Construct a binary tree by traversing pre-order and middle-order sequences
This problem is also a pretty good problem, and in fact when we learn about data structures, this problem often comes up in the way of solving problems, let’s do it on the exam, it’s really impressive, here, let’s see how to solve it in code.
It’s the same routine, the same idea, the same taste, let’s cook this dish again.
First of all, determine whether preordered traversal, middle-ordered traversal or post-ordered traversal, since it is derived from preordered traversal and middle-ordered traversal, so, preordered traversal is better.
So we’re going to think straight about what we’re going to do, and we’re going to go straight to the dish.
Current Step: Recall before doing the thinking of this topic you will find that we have to construct the binary tree, the idea is that the preorder traversal of the first element must be the root node a, so, the current a preorder traversal of the element, in the sequence traversal, in a this element on the left side is the left subtree of elements, in the element to the right of the element is left a subtree of elements, The only thing we need to do is find the element A in the middle order traversal, and we can do the rest recursively.
Without further ado, look at the code.
public TreeNode buildTree(int[] preorder, int[] inorder) {
// The first element of the current preorder traversal
int rootVal = preorder[0];
root = new TreeNode();
root.val = rootVal;
// Get the position in the sequence traversal group in inorder
int index = 0;
for(int i = 0; i < inorder.length; i++){
if(rootVal == inorder[i]){ index = i; }}// do it recursively
}
Copy the codeNow that we’ve done that, it’s time to recurse and let the computer do the work.
public TreeNode buildTree(int[] preorder, int[] inorder) {
// The first element of the current preorder traversal
int rootVal = preorder[0];
root = new TreeNode();
root.val = rootVal;
// Get the position in the sequence traversal group in inorder
int index = 0;
for(int i = 0; i < inorder.length; i++){
if(rootVal == inorder[i]){ index = i; }}// do it recursively
root.left = buildTree(Arrays.copyOfRange(preorder,1,index+1),Arrays.copyOfRange(inorder,0,index));
root.right = buildTree(Arrays.copyOfRange(preorder,index+1,preorder.length),Arrays.copyOfRange(inorder,index+1,inorder.length));
return root;
}
Copy the codeFinally, handle the boundary conditions to prevent root from being null.
TreeNode root = null;
if(preorder.length == 0) {return root;
}
Copy the codeOk, this dish just follows the template, trust you, you will copy the rest of the dish stir-fry.
Look at DFS from leetcode’s island problem
Step by step
There are a lot of such questions in Leetcode, and you will often encounter such questions in the written test, so it is very important to find a way to solve them. In fact, in the end, you will find that these questions are no longer difficult after you know them.
Let’s look at the problem first.
So what they’re saying is very simple, you have a two-dimensional array of numbers 0 and 1, 0 for water, 1 for land, and they’re asking you to count the number of land, the number of islands.
So how to solve this kind of problem?
In fact, we can look at this problem from the above mentioned binary tree DFS problem, binary tree characteristics are obvious, is only two branches can choose.
Hence, the following traversal template.
// preorder traversal
void traverse(TreeNode root) {
System.out.println(root.val);
traverse(root.left);
traverse(root.right);
}
Copy the codeHowever, if you go back to the problem, you will see that our entire data structure is a two-dimensional graph, as shown below.
When you walk through this graph, how do you walk through it? Is that it?
At (I, j), can there be four directions that can be traversed, so that gives us a new way to solve this problem.
So we can write the DFS template code for this.
void dfs(int[][] grid, int i, int j) {
// Access up, down, left, and right adjacent directions
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
}
Copy the codeAnd you’ll see that it’s very similar to traversal of a binary tree, but with two more directions.
The last thing we need to consider is the base case. Actually, we need to talk about the base case of binary trees, but it is very simple, when root == null, it is the base case.
In fact, the base case here is not difficult, because this two-dimensional graph has a boundary. When DFS finds that it is beyond the boundary, it is necessary to judge whether it is beyond the boundary. Therefore, boundary conditions are added.
void dfs(int[][] grid, int i, int j) {
// Base case
if(! inArea(grid, i, j)) {return;
}
// If the cell is not an island, return directly
if(grid[i][j] ! =1) {
return;
}
// Access up, down, left, and right adjacent directions
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
}
// Check whether coordinates (r, c) are in the grid
boolean inArea(int[][] grid, int i, int j) {
return 0 <= i && i < grid.length
&& 0 <= j && j < grid[0].length;
}
Copy the codeSo at this point we’re almost done with this problem, but there’s one other thing we need to be aware of, is that when we visit a node, we need to tag it, either with bool or with some other number, otherwise we’re going to end up with recursive loops.
So, we have our final solution.
void dfs(int[][] grid, int i, int j) {
// Base case
if(! inArea(grid, i, j)) {return;
}
// If the cell is not an island, return directly
if(grid[i][j] ! =1) {
return;
}
// Use 2 to mark traversal
grid[i][j] = 2;
// Access up, down, left, and right adjacent directions
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
}
// Check whether coordinates (r, c) are in the grid
boolean inArea(int[][] grid, int i, int j) {
return 0 <= i && i < grid.length
&& 0 <= j && j < grid[0].length;
}
Copy the codeNot enough? Let’s do another one.
2. Do it again
This is very similar to the previous problem, but this is the area of the largest island, and since the area of each cell is 1, the final area is the number of cells.
The solution to this problem is basically the same as the one above, so let’s just copy the code above and change it.
class Solution {
public int maxAreaOfIsland(int[][] grid) {
if(grid == null) {return 0;
}
int max = 0;
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[0].length; j++){
if(grid[i][j] == 1){ max = Math.max(dfs(grid, i, j), max); }}}return max;
}
int dfs(int[][] grid, int i, int j) {
// Base case
if(! inArea(grid, i, j)) {return 0;
}
// If the cell is not an island, return directly
if(grid[i][j] ! =1) {
return 0;
}
// Use 2 to mark traversal
grid[i][j] = 2;
// Access up, down, left, and right adjacent directions
return 1 + dfs(grid, i - 1, j) + dfs(grid, i + 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1);
}
// Check whether coordinates (r, c) are in the grid
boolean inArea(int[][] grid, int i, int j) {
return 0 <= i && i < grid.length
&& 0 <= j && j < grid[0].length; }}Copy the codeThe basic idea: Each time you do DFS, add +1 to the number of islands, and then find the maximum of all islands.
Let’s see how efficient our code is.
Doesn’t it look good, yeah, that’s how things work!!
In the end, it took me almost a week to write this article back and forth. I don’t know how I went about it, but I tried my best to express clearly what I thought. It was mainly a way of thinking and a way to solve the problem.
Ok, I have written long enough, I will look at the others in the next article, I hope they are helpful, see you again!
Finally, I would like to share the Java interview + Java backend technology learning guide that I summarized for three months, which is my summary of these years and spring recruitment. I have received the offer from a big factory and organized it into an e-book. Please take it as follows:
Now free to share everyone, in the following my public number programmer’s technical circle reply interview can be obtained.
