This article is participating in the nuggets team online activity, clickCheck spring recruitment positions in big factories

Writing algorithms is a must in an interview. One of the characteristics of the algorithm is that if you have done, if you have ideas, you can do it quickly; If you haven’t done it, it’s a test of improvisation. I am in the interview sometimes because of nervous, see algorithm problem is afraid of, finally affect the interview result 😓.

Therefore, we should pay attention to strengthen the training of the algorithm at ordinary times. In the process of doing the algorithm, we should precipitation our ideas of solving the problem, classify and transform the problem, and do everything.

Share the experience of learning algorithms

Here I would like to share my experience in the process of brush algorithm:

1. Develop good study habits

  • Encounter difficulties, repeatedly thinking and understanding
  • Three points for understanding and seven points for practice

Avenue to simple, thinking about the essence, find the inner repeatability

Pay attention to summary and induction, and then see similar problems can be associated with the corresponding solution. Such as:

  • When you have a tree problem, you can think of depth-first tree traversal, breadth-first tree traversal, and depth-first traversal is recursion, breadth-first traversal is loop + store array
  • Encountered linked list can think of the solution idea has traversal + mark
  • When encountering a palindrome, flip the array, flip the number to think of a double pointer + swap
  • . There are many more scenarios to summarize

Ditch old habits

  • Don’t knock (5 minutes do not come out to see the problem solution, full understanding is the key)
  • Don’t just do it once, brush the same question five times.
  • Not lazy to see the master code

As long as you master the law of the algorithm, usually more summary accumulation, later encountered algorithm, we are not afraid of ~

Tree dependent algorithm

Here I collected a wave of tree algorithm questions, but also in order to put the same type of questions together to compare, summarize the internal law.

Organized topic

classification The difficulty The title
DFS simple 104. Maximum depth of a binary tree
DFS simple 111. Minimum depth of a binary tree
BFS medium 102. Sequence traversal of binary trees
BFS medium 107. Sequence traversal of binary trees II
DFS simple 226. Flip the binary tree
DFS simple 101. Symmetric binary trees

instructions

DFS: depth-first traversal

BFS: breadth-first traversal

To the problem solving

1. Create a tree

Do the tree algorithm to create a tree structure, below provides the node method to create a tree.

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))
let head = node(7, left, right)
Copy the code

2. Maximum depth of binary tree

Forced-link: 104. Maximum depth of binary tree

Thought analysis

The maximum depth of a tree involves traversing 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 ways are used to calculate the tree depth.

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 the code

Method 2. Breadth-first traversal

Using breadth first to calculate the depth of the tree is a bit more complicated to implement. Note the following points:

  1. Use an array to hold each node

  2. Use two Pointers, I to the current index and last to the last item of the current layer

  3. Pay attention to the condition of hierarchy 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 the code

Complexity analysis

The students who do not have a class background often have a little muddled circle to the concept of time complexity and space complexity 😶, in fact, time complexity is the number of calculation, calculation is a few times. The spatial complexity is the number of additional variables used in the calculation. The traversal of the tree is generally to traverse the entire tree structure, and the time complexity is O(n), where n is the number of nodes in the tree. The space complexity depends on the stack space used, which is O(n).

Time complexity:O(n)

Space complexity:O(n)

3. The minimum depth of the binary tree

Force link: 111. Minimum depth of binary tree

Thought analysis

I’m going to go straight to DFS for this, and you can think about what you would do with BFS for breadth first. Because the interviewer sees that you are doing well, sometimes he or she will raise the bar and extend the question. We should think twice, too.

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 the code

4. Breadth-first traverse

Force link 1:102. Sequence traversal of binary tree

Force link 2:107. Sequence traversal of binary trees II

Both of these are breadth-first traversal problems, and thinking about them together can help you understand them better. There are variations on this type of problem, such as asking to return the sum of nodes at each level.

Thought analysis

The core idea of breadth-first traversal is the while loop + array. Create an array, store the root node in the array, iterate over each node in the array, and add child nodes, if any, to the end of the array until the end of the array.

AC code

Problem 1:102. Sequence traversal of binary trees

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 the code

Problem 2:107. Sequence traversal of binary trees 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) {
      // At the end of the current layer
      lastIndex = array.length - 1
      res.unshift(temp)
      temp = []
    }
    i++
  }
  return res
}
Copy the code

5. Flip the binary tree

Force link: 226. Flip the binary tree

Thought analysis

DFS (depth-first) is used to traverse the binary tree, swapping each node. The core idea here is recursion + interchange

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 the code

6. Symmetric binary trees

Force-link: 101. Symmetric binary trees

Thought analysis

This problem can be solved by a depth-first traversal (recursive) approach.

For example, if we look at the following two subtrees (they are the left and right subtrees of the root node respectively), we can observe the following rule:

  • Left child of left subtree 2 == right child of right subtree 2;
  • The right child of left subtree 2 == the left child of right subtree 2
    2         2/ \ \3   4     4   3/ \ / \ / / \8  7 6  5 5  6 7  8
Copy the code

We call the left subtree of the root node left and the right subtree right. Check if left equals right, if not, return right. If they are equal, compare the left node with the right node, and then compare the left node with the left node

Two conditions for recursive functions can be summarized based on the above information:

  1. The terminating condition is either left or right, or both left and right are empty
  2. Recursively comparing left, left and right. Right, recursively comparing 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 the code

conclusion

In the case of trees, we think of depth-first or breadth-first traversal of trees. Depth-first traversal is recursion, breadth-first traversal is loop + array. In the interview can first think of the mind of these points out of the set, to see if you can solve, to avoid the situation without a clue.