Writing in the front
Data structure and algorithm:
Brush don’t know if you have this kind of confusion, although a lot of algorithm, when I went to the interview, the interviewer let you write an algorithm that may be you are very familiar with this algorithm, know the implementation mentality, but always don’t know where is the writing, and many boundary conditions are not comprehensive, a nervous, code written in a mess. If you encounter an algorithm that you haven’t done before, you don’t know where to look. After I suffered a loss in the interview, I slowly made a summary and began to classify all the question types and problem-solving ideas of the data structure and write a systematic summary of the weekly brush questions on Github. Welcome to Star: “Data Structure and Algorithm Warehouse”
PS: If you are just learning data structures and algorithms, please be sure to understand the simplest questions, all the entry data structures and algorithms from simple to complex are comprehensively combed. “30 Data Structures and Algorithms for Beginners”
If you have a certain understanding and understanding of data structure and algorithm, the above introductory algorithm problems can be easily implemented, then you can try to solve the 30 problems summarized in LeetCode. I have made a detailed arrangement of problem solving ideas, test cases, code implementation, and suggest that you try to solve it yourself first. Welcome to Star. “30 LeetCode Classic Algorithm Questions to Know”
Network protocol principle:
In addition to the algorithm, the most attention is the network principle, the interview because I suck itself on the school, class is just a bit fur, at that time, didn’t also attaches great importance to this piece, so at a junior interview ate a big loss, and then began to attach importance to it, though this part of the theory, but from the most basic began to learn need a guide, TCP and HTTP, it must be difficult to learn. Then I tried to learn the principle of network from the root, why there are these, so while learning, while sorting out the article to share to learn the principle of network this piece of content, Github will update every week ~ “dig here to check the repository”
— The following is the text —-
“Sword finger offer” is a good book to prepare for the interview of data structure and algorithm. There are a lot of questions that should be paid attention to in the interview of handwriting algorithm, but they are basically implemented in C++. The classification of each chapter in the book is classified according to the performance and consumption as well as the attention of handwritten code. The hybrid realization of data structure and algorithm is carried out.
Brush twice, found that can also be sorted out and classified according to their own situation. All codes are written in JS, which have been tested by Leetcode standard (a small number of topics that Leetcode does not have). The characteristics of all algorithm questions are summarized and classified, and how to take all boundary conditions into account in handwriting algorithm; If multiple ideas are quickly solved, how to quickly convert ideas into code, which is the focus of this article to share.
There are a total of 11 binary tree problems, I put the 11 problems in the book to implement methods and ideas have a detailed explanation, but for individuals, in the future encounter strange binary tree problems how to solve, through the analysis of 11 questions, sorting out the following steps, first look at the 11 binary tree classic algorithm questions.
PS: If you’ve already done these questions and can write them out by hand, slide to the bottom, and hopefully the binary tree ideas, test cases, and code summary will help you in your interview (the best part of this article).
11 essential binary tree interview questions
1.1 Interview question 7: Rebuilding binary trees
Known for preorder traversal,2,4,7,3,5,6,8 {1}, in sequence traversal for,7,2,1,5,3,8,6 {4}, the binary tree is?
1, the train of thought
According to the characteristics of pre-order traversal, (left-right root, left-right root), first determine the root node according to the pre-order traversal, and then know the number of left and right trees of the root node in the middle-order traversal, and inverse deduce the nodes of the left subtree in the pre-order traversal. The reconstruction of binary tree can be completed by recursion according to this idea.
2. Test cases
- Complete binary tree, incomplete binary tree — general test.
- Binary tree with only left child node and one node with only right child node — special binary tree test.
- Empty tree, preorder and middle order mismatch — input test.
3. Code implementation
1 // Define the node
2 // class TreeNode{
3 // constructor(data){
4 // this.data = data;
5 // this.left = null;
6 // this.right = null;
7 / /}
8 // }
9
10 // Parameters: pre-order traversal number group to mid-order traversal number group
11 const reConstructBinaryTree = (pre, vin) = >{
12 // Check whether the pre-ordinal group and the middle ordinal group are empty
13 if(! pre || pre.length ===0| |! vin || vin.length ===0) {14 return;
15 }
16 // Create the root node of the binary tree
17 var treeNode = {
18 val: pre[0]
19 }
20 // Find the root node in the sequence traversal
21 for(var i = 0; i < pre.length; i++) {
22 if (vin[i] === pre[0]) {
23 // Split the pre-middle traversal of the left subtree
24 treeNode.left = reConstructBinaryTree(pre.slice(1, i+1), vin.slice(0, i));
25 // Split the right subtree's pre-middle traversal
26 treeNode.right = reConstructBinaryTree(pre.slice(i+1),vin.slice(i+1));
27 }
28 }
29 // Returns the root node
30 return treeNode;
31 }
32
33 let pre = [1.2.4.7.3.5.6.8]; // preorder traversal
34 let vin = [4.7.2.1.5.3.8.6]; // middle order traversal
35 console.log(reConstructBinaryTree(pre,vin));
Copy the code
1.2 The next node of the binary tree
Given a node of a binary tree, how to find the next node of the order traversal. There are two Pointers to the left and right subtrees and one pointer to the parent node.
8. [答 案]
1.3 Tree substructure
Input two binary trees A and B to determine whether B is A substructure of A.
Question 26: [A].
1.4 Binary tree mirroring
Please complete a function, if a binary tree, the function output its mirror image.
Question 27: What is the meaning of this passage?
1.5 Symmetric binary tree
Implement a function to determine whether a binary tree is symmetric. A binary tree is symmetric if it is the same as its mirror image.
Question 28: What is the meaning of this passage?
1.6 Printing binary trees from top to bottom
Each node of the binary tree is printed from top to bottom, and nodes of the same level are printed from left to right. (Traversing the binary tree by layer)
Question 32:
1.7 Post-order traversal sequence of binary tree
Enter an array of integers to determine if the array is a subsequent traversal of a binary search tree. Return true if it is, false if it is not. Suppose any two numbers in the input are different.
Question 33:
1.8 Binary tree sum is a valued path
Enter a binary tree and an integer, and print out the sum of node values in the binary tree as all paths to the output integers. A path is formed from the root of the tree down to the nodes passed by the leaf.
[答 案]
1.9 Serializing binary trees
Implement two functions to serialize and deserialize the binary tree.
Question 37: [A].
1.10 The KTH largest node of the binary tree
Given a binary search tree, find the KTH large node in it.
54. [答 案]
1.11 Depth of binary tree
Enter the root node of a binary tree to find the depth of the tree. Nodes (including root and leaf nodes) that pass from root to leaf form a path in the tree. The length of the longest path is the depth of the tree.
Question 55: What is the meaning of this passage?
summarizing
By the sword refers to offer more than eleven, not done then I remembered that simple, but through the above binary tree topic summarized, can extrapolate, summed up the binary tree interview question their thinking, meet after binary tree face reading questions can be summed up the above steps to think independently to solve, this is the focus of this article. Here’s an in-depth summary of how to solve problems, test cases, and write code.
1. Summary of solving ideas
1. Solve the problem according to the rule of order traversal in front of the tree (root left and right), middle (left and right root) and rear (left and right root).
Through the traversal of binary tree to find the rule, so as to find the solution of the problem.
-
Rebuild the binary tree
According to the preceding and middle order traversal, the root node and the rule of the left and right subtrees of the binary tree are found, and then the binary tree is constructed recursively.
-
The next node in the binary tree
According to the order traversal, find out all possible cases of the next node containing any node, and then judge according to the case respectively.
-
The subsequent traversal sequence of a binary tree
The rule of printing binary tree nodes can be found by middle-order traversal, and whether the subsequent traversal is a binary tree can be judged.
-
The binary tree sum is a path of some value
Choose binary tree traversal, storage judgment for each node, and then according to the characteristics of binary tree leaf nodes, to solve the problem.
-
The KTH largest node of the binary tree
The result of middle order traversal is from small to large, and then find the KTH big data backwards.
-
Serialize binary trees
Traversing the binary tree, null is converted to a special symbol.
2, according to the structure of the tree to find rules to solve the problem
Through the characteristics of binary tree: the left child node is smaller than the parent node, the right child node is larger than the parent node, the nodes of the tree can carry out recursion, etc., the above characteristics are better to help us solve the idea.
-
Substructure of a tree
According to the characteristics of substructure and main tree, we can find the way to solve the problem by analyzing its tree structure.
-
Mirrored binary tree
By observing the characteristics of the left and right child nodes of the mirror binary tree, we can find the way to solve the problem.
-
Symmetric binary tree
Observe the characteristics of symmetric binary tree, find the characteristics and rules in the structure and ergodic, can find the solution of the problem.
-
Traverse the binary tree layer by layer
According to the structural relationship (parent-child relationship) of nodes at each layer of the binary tree, each layer can be traversed, and the traversal nodes at the lower layer can be found through the upper layer.
-
Deserialize the binary tree
According to the rules of traversal and binary tree, a binary tree is generated from traversal results.
Test cases
Through the above questions, I have divided test cases into three categories, and when testing code, it is ok to think in these three categories.
- Common test
- Special test
- The input test
1. General tests
The common test is thought from two aspects. The first aspect is the problem itself, such as the judgment of symmetric binary tree. The common test is to input a symmetric binary tree and an asymmetric binary tree respectively. The second aspect is that the problem itself has no tests to find, such as traversing the binary tree by layer. Its normal test is to input complete binary trees (ordinary binary trees are also ok), and incomplete binary trees to test.
2. Special tests
Special tests emphasize the particularity of trees. There are only a few special binary trees, such as: binary trees with only left child nodes, binary trees with only right child nodes, binary trees with only one node, and binary trees with no nodes.
3. Input tests
An input test, as its name suggests, evaluates the parameters that the user has entered. For example, if you enter a tree, you need to determine whether it is empty. Another example is to find the maximum K node and judge the value range of K.
Third, code writing
In addition to proficient in the most basic binary tree increase, delete, change, search, the most important is the recursion of binary tree, because the structure of binary tree determines the use of recursion to solve the problem of binary tree is more convenient. However, writing recursion is not simple, because it involves the process of recursion and recursion, and the brain is not able to deal with these better. You can see the previous article summarizing recursion “Recursive Series of Data Structures and Algorithms”.
One of the things that’s particularly important when writing binary tree recursions is not to try to think about the recursion, but to find the termination condition of the recursion, and then judge the result of each recursion, and then let it recurse. Again, don’t think about the recursion.
Afterword.
Brush the offer for a second, third, and fourth time after failing to grasp the essence of these questions. Gradually summarize the same type of questions. In the first week, I completed the summary of all binary tree interview questions, and in the next week, I will choose the next type of interview questions to conquer. I plan to spend two months to systematically summarize and summarize all interview questions of sword point offer, and share them while learning. “Jab the sword at the Offer warehouse and punch in with me”
❤️ Don’t forget to leave your learning footprints[Likes + Favorites + comments]
All see the article not praise are “play rascal”, hey hey ヾ(◍°∇°◍) Blue! Just as a joke, move your little hands and click “like”, each of you will make more learners join in with a contribution (like + comment)! Thank you very much! ￣ ￣ omega =
The author Info:
Author: Deer
Introduction to Programming: I learned programming from the ground up with the students of Little Deer in the way of animation, and presented the Web front-end domain, data structure and algorithm, network principle and other easy to understand to my friends. Reproduced description: reproduced please state the source [juejin.cn/post/684490…] Thank you for your cooperation.