This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

71. Binary-tree-inorder-traversal

The label

  • Binary tree traversal
  • simple

The title

Leetcode portal

Let’s just open leetCode.

Given the root node of a binary tree, return its middle-order traversal.

Input: root = [1,null,2,3]Copy the code

The basic idea

Eldest brother this article wrote very clear and detailed, do not repeat. Pre-order/middle-order/post-order traversal of a binary tree

Writing implement

  • The recursive implementation
const midOrderTraversalRecursion = (root) = > {
  let resList = []
  const midOrderTraversal = (node) = > {
    if(node ! = =null) {
      // Iterate through the left subtree
      midOrderTraversal(node.left)           // --------->
      // Then access the root node
      resList.push(node.val)                 // ---------> (root)
      // Walk through the right subtree again
      midOrderTraversal(node.right)          // --------->
    }
  }
  midOrderTraversal(root)
  return resList
}
Copy the code
  • Iteration implement
const midOrderTraversalIteration = (root) = > {
  const resList = []
  let stack = []
  let curNode = null

  if(root ! = =null) {
    curNode = root
  }

  // Loop when the stack is not empty or the current node is not empty
  while (stack.length > 0|| curNode ! = =null) {
    // In order to traverse, first access the left subtree => then the root => then the right subtree
    while(curNode ! = =null) {
      // We have to push the current node to its left subtree
      stack.push(curNode)
      curNode = curNode.left
    }
    if (stack.length > 0) {
      // Get something from the stack, push the top out first
      curNode = stack.pop()
      // Enter data into the result sequence
      resList.push(curNode.val)
      // Set the current node to its right subtree
      curNode = curNode.right
    }
  }
}
Copy the code

This may look like a face of confusion, simply put the following steps, try to understand

  1. The root node is pushed first, and if it has a left node, the left node is pushed until the current pushed node has no left subtree, so it can be understood that the current is the leftmost node
  2. Out of the stack, the top of the stack is the leftmost node just pushed and prints the leftmost node
  3. If the leftmost node has a right subtree, then the right subtree should be accessed at the moment, because this node has no left child. Now it is printed as the root itself. Here is the right subtree accessing the left root right
  4. So, the current node becomes the right subtree, and the loop ends
  5. Go through the next loop using the current right subtree as the root that came in first
  6. I’m going to start from the first step, see if there’s a left subtree and I’m going to go to the leftmost node of this node and I’m going to go to the leftmost node of this node…

72. Different binary search trees II (unique-binary search- trees-II)

The label

  • DFS
  • BST (binary-search-trees)
  • medium

The title

Leetcode portal

Let’s just open leetCode.

Given an integer n, generate all values determined by 1… N is the binary search tree composed of nodes.

Input: 3 Output: [[1, NULL,3,2], [3,2, NULL,1], [3,1, NULL, NULL,2], [2,1,3], [1, NULL,2, NULL,3] 1 1 2 2 1 / / / \ \ 3 2 1 1 2 2 / / \ \ 2 2 2 3Copy the code

The relevant knowledge

The key property of binary search tree BST(binary search-trees) is

  1. The root nodeThe value of theIs greater thanThe left subtreeValues of all nodes
  2. The root nodeThe value of theLess thanThe right subtreeValues of all nodes
  3. The left and right subtrees are also binary search trees

Then there’s divide-and-conquer

Divide and conquer: “divide and conquer” – is to divide a complex problem into two or more identical or similar sub-problems, until the sub-problems can be solved directly, the solution of the original problem is the combination of the solutions of the sub-problems.

The basic idea

When we want to generate all feasible binary search trees, assuming that the current sequence length is N, we take each element, from left to right, as the root, as the base, and the value is I. Then, according to the properties of binary search trees, we can know that the set range of node values of the left subtree is [1, I − 1]. The set range of the node values of the right subtree is [I + 1, n], so we can continue to divide and conquer left and right, because the left side [1, I − 1] is actually a subset of the total problem, and finally merge the solutions.

Basic steps

  1. dfs (left, right)The return value of this function is represented in[left, right]Scope all subtree cases.
  2. Each number goes from left to right, for any one of themi, all the subtree cases generated by the left interval, which is actually DFS (left, i-1), isA subproblem of the general problem.
  3. Each number goes from left to right, for any one of themi, all subtrees generated in the left interval areleftTrees, all subtrees generated in the right interval arerightTreesSo the number of cases is going to be the number of casesThe product of.
  4. Generate BST advancing RES in various cases

Writing implement

let generateTrees = function(n) {
  const dfs = (left, right) = > {
    // It is already to the bottom
    if (left > right) {
      return [null]}let res = []

    for (let i = left; i <= right; i++) {
      // I is the index currently used as the root
      let leftTrees = dfs(left, i - 1)
      let rightTrees = dfs(i + 1, right)
      // The following is the cartesian product of sets
      for (let leftTree of leftTrees) {
        for (let rightTree of rightTrees) {
          let root = new TreeNode(i);
          root.left = leftTree
          root.right = rightTree
          res.push(root)
        }
      }
    }

    return res;
  }
  return dfs(1, n);
}

console.log(generateTrees(3))

Copy the code

In addition, I would like to recommend the article of the eldest brother to you. It is very simple and profound. It is very effective for the students who advance in the front end. Core concepts and algorithm disassembly series

That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me presious tower shock the rever monster, I see it through, the code is not on the ha, add after I will do my best to help you, but pay attention to the way of asking questions, suggest reading this article first: the wisdom of asking questions

reference