Summarize the algorithmic questions of a wave of trees to help you ride the wind and waves in the interview |

Summarize the algorithmic questions of a wave of trees to help you ride the wind and waves in the interview |

This article is participating Nuggets team number on-line 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 on-the-spot 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 problem-solving 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 depth-first traversal and breadth-first traversal of the tree , while depth-first traversal thinks of recursion , and breadth-first traversal is loop + storage array
  • The problem-solving 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~

Tree-related 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

classificationDifficultytopic
DFSsimple104. Maximum depth of binary tree
DFSsimple111. The minimum depth of a binary tree
BFSmedium102. Sequence traversal of binary tree
BFSmedium107. Sequence Traversal of Binary Tree II
DFSsimple226. Flip Binary Tree
DFSsimple101. 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

node
Method to create a tree.

/* 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: depth-first traversal and breadth-first traversal. The following two methods are used to calculate the depth of the tree.

Method 1. Depth-first 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. Breadth-first traversal

Use breadth-first to calculate the depth of the tree, which is slightly more complicated to implement. Note the main points:

  1. Use an array to save each node

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

  3. Pay attention to the conditions of level switching [key]

    if (i == last) {last = arr.length-1 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 non-major 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 breadth-first 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 breadth-first 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 depth-first 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:

  1. The termination condition is: left and right are not equal, or both left and right are empty
  2. 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 depth-first traversal or breadth-first traversal of the tree . While depth-first traversal thinks of recursion , breadth-first 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.