This article is participating Nuggets team number online activity, click to see giant spring recruit jobs
Writing algorithms in the interview is a must. One of the characteristics of algorithmic questions is that if you have done it and have ideas, you will be able to do it soon; if you have not done it, it will be a test of onthespot performance. I sometimes get nervous during the interview, and I see algorithmic questions getting frustrated, which ultimately affects the interview results .
Therefore, we must pay attention to the training of algorithms in normal times, precipitate our own problemsolving ideas in the process of doing algorithmic problems, classify and transform problems, and achieve one pass.
Share the experience of learning algorithms
Here I share the experience I summarized in the process of brushing algorithmic questions:
1. Develop good study habits
 When encountering difficulties, think and understand repeatedly
 3.points for comprehension, seven points for practice
2. From the avenue to the simplicity, think about the essence and find the inner repetitiveness
Pay attention to the summary, and then you can think of the corresponding solution when you see similar questions. such as:
 When encountering tree problems, you can think of depthfirst traversal and breadthfirst traversal of the tree , while depthfirst traversal thinks of recursion , and breadthfirst traversal is loop + storage array
 The problemsolving ideas that can be thought of when encountering a linked list have traversal + mark
 When encountering a palindrome, flipping the array, flipping the number, think of double pointer + swap
 ... There are still many scenes, a lot of summary
3. Abandon old habits
 Don t stubbornly (see the solution if you can t do it in 5 minutes, full understanding is the key)
 Don t just do it once, brush each question five times (5.Poison Palms)
 Not too lazy to look at the master code
As long as we have mastered the laws of algorithmic questions, we usually sum up and accumulate more, and we will not be afraid when we encounter algorithmic questions in the future~
Treerelated algorithm problems
Here I have collected a wave of tree algorithm questions, also to compare the same types of questions together and summarize the internal laws.
Sorted questions
classification  Difficulty  topic 

DFS  simple  104. Maximum depth of binary tree 
DFS  simple  111. The minimum depth of a binary tree 
BFS  medium  102. Sequence traversal of binary tree 
BFS  medium  107. Sequence Traversal of Binary Tree II 
DFS  simple  226. Flip Binary Tree 
DFS  simple  101. Symmetric Binary Tree 
Description
DFS: Depth First Traversal
BFS: Breadth First Traversal
Start to solve the problem
1. Create the tree
To make tree algorithm problems, you must first create a tree structure, which is provided below
/*
The tree structure is as follows
7
3 6
1 2 4 5
*/
function node ( val, left = null , right = null ) {
return {
val,
left,
right,
}
}
let left = node( 3 , node( 1 ), node( 2 ))
let right = node( 6 , node( 4 ), node( 5 ))
the let head = Node ( . 7 , left, right)
copy the code
2. The maximum depth of the binary tree
Power button link: 104. The maximum depth of the binary tree
Thinking analysis
The maximum depth of the tree involves the traversal of the tree, and the height of the tree can only be calculated after traversing the entire tree. There are two kinds of tree traversal: depthfirst traversal and breadthfirst traversal. The following two methods are used to calculate the depth of the tree.
Method 1. Depthfirst traversal
let maxDepth = function ( root ) {
if (root == null ) {
return 0
} else {
let left = maxDepth(root.left)
let right = maxDepth(root.right)
return Math .max(left, right) + 1
}
}
Copy code
Method 2. Breadthfirst traversal
Use breadthfirst to calculate the depth of the tree, which is slightly more complicated to implement. Note the main points:

Use an array to save each node

Use two pointers, i points to the current index, last points to the last item of the current layer

Pay attention to the conditions of level switching [key]
if (i == last) {last = arr.length1 height++}
function maxDepth ( node ) {
if (!node) return 0
let arr = [node],
i = 0 ,
last = 0 ,
current,
height = 0
while (i <arr.length) {
current = arr[i]
if (current.left) {
arr.push(current.left)
}
if (current.right) {
arr.push(current.right)
}
if (i == last) {
last = arr.length 1
height++
}
i++
}
return height
}
Copy code
Complexity analysis
Students from nonmajor classes are often confused about the concept of time complexity and space complexity. In fact, time complexity is the number of calculations, and the number of calculations is just a few. Space complexity is the number of additional variables used in the calculation process. When it comes to tree traversal, it is generally necessary to traverse the entire tree structure. At this time, the time complexity is O ( n ), where n is the number of nodes in the tree; the space complexity is related to the stack space used, which is O ( n ) .
Time complexity: O ( n )
Space complexity: O ( n )
3. The minimum depth of the binary tree
Link link: 111. The minimum depth of the binary tree
Thinking analysis
I will use DFS (depth first) to solve this problem directly, and you can also think about how to do it with BFS (breadth first) in the process of doing the problem. Because the interviewer sees you doing well, sometimes it will increase the difficulty and extend the question. We should also think more and stay behind.
AC code
let minDepth = function ( root ) {
if (root == null ) {
return 0
} else {
let left = minDepth(root.left)
let right = minDepth(root.right)
return Math .min(left, right) + 1
}
}
Copy code
4. Breadth first traversal
Likou link 1: 102. Sequence traversal of binary tree
Likou Link 2: 107. Sequence Traversal of Binary Tree II
These two questions are breadthfirst traversal questions. Thinking of these two questions together can deepen your understanding. This type of question can also be modified, such as requiring the return of the sum of each layer of nodes.
Thinking analysis
The core idea of breadthfirst traversal is while loop + array. Create an array, save the root node in the array, and then traverse each node in the array. If there are child nodes, add them to the end of the array until the end of the traversal.
AC code
Question 1: 102. Sequence traversal of binary tree
var levelOrder = function ( root ) {
if (!root) return []
let resArr = [],
array = [root],
i = 0 ,
levelLastIndex = 0 ,
temp = []
while (i <array.length) {
let current = array[i]
if (current.left) {
array.push(current.left)
}
if (current.right) {
array.push(current.right)
}
temp.push(current.val)
if (i == levelLastIndex) {
levelLastIndex = array.length 1
resArr.push(temp)
temp = []
}
i++
}
return resArr
}
Copy code
Question 2: 107. Sequence traversal of binary tree II
var levelOrderBottom = function ( root ) {
if (!root) return []
let array = [root],
i = 0 ,
lastIndex = 0 ,
temp = [],
res = []
while (i <array.length) {
let current = array[i]
if (current.left) {
array.push(current.left)
}
if (current.right) {
array.push(current.right)
}
temp.push(current.val)
if (i == lastIndex) {
//The last item in the current layer
lastIndex = array.length 1
res.unshift(temp)
temp = []
}
i++
}
return res
}
Copy code
5. Flip the binary tree
Power button link: 226. Flip the binary tree
Thinking analysis
Use DFS (depth first) to traverse the binary tree and exchange each node. The core idea here is recursion + exchange
AC code
var invertTree = function ( root ) {
if (!root) return root
invertTree(root.left)
invertTree(root.right)
let temp = null
temp = root.left
root.left = root.right
root.right = temp
return root
}
Copy code
6. Symmetric Binary Tree
Power button link: 101. Symmetric Binary Tree
Thinking analysis
This problem can be solved by the idea of depthfirst traversal (recursion).
For example, look at the following two subtrees (they are the left subtree and the right subtree of the root node, respectively), and you can observe such a rule:
 Left child of left subtree 2 == right child of right subtree 2;
 Right child of left subtree 2 == left child of right subtree 2
2 2
////
3 4 4 3
////////
. 8 . 7 . 6 . 5 . 5 . 6 . 7 . 8
copy the code
We mark the left subtree of the root node as left and the right subtree as right. Compare whether left is equal to right, if not, just return directly. If they are equal, compare the left node of left with the right node of right, and then compare the right node of left with the left node of right
According to the above information, two conditions of recursive function can be summarized:
 The termination condition is: left and right are not equal, or both left and right are empty
 Recursively compare left, left and right.right, recursively compare left, right and right.left
AC code
function isSymmetric ( root ) {
return isMirror(root.left, root.right)
function isMirror ( node1, node2 ) {
if (node1 === null && node2 === null ) {
return true
}
if (node1 === null  node2 === null ) {
return false
}
return (
node1.val === node2.val &&
isMirror(node1.left, node2.right) &&
isMirror(node1.right, node2.left)
)
}
}
Copy code
summary
When encountering the problem of trees, we have to think of depthfirst traversal or breadthfirst traversal of the tree . While depthfirst traversal thinks of recursion , breadthfirst traversal is loop + array . In the interview, you can first put out these points in your mind and see if you can solve them, so as to avoid the situation where you don't have a clue.