I am an algorithm residue, the content for the individual in the practice algorithm brush problem record. Record some personal understanding of the solution of the problem summary. If wrong welcome to correct!

1. Preorder traversal of binary tree

144. Antecedent traversal of binary trees

describe

Give you the root node of the binary tree, root, and return a pre-traversal of its node value.

Example:

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

The recursive method

  • Answer:
    • The recursive solution is easy to understand, according to the order of the preceding traversal:Root -> left -> right; The recursive traversal process of binary tree can be decomposed into:
      • Save the current root value
      • Traverses the left subtree to obtain the traversal result of the left subtree and merge it with the root node (the root node value should be in front of the traversal result of the left subtree according to the preceding traversal order)
      • Traversal the right subtree, get the traversal result of the right subtree and merge with the above result
    • The recursiverecursiveIt is to traverse the whole tree, separate the root node, divide the tree into left and right subtrees, and then solve the traversal problem of left and right subtrees. The traversal problem of left and right subtrees can be divided into left and right subtrees as just described, and then solve the small problem of splitting
    • whileBelong to theIs the content that needs to be returned after encountering the termination condition. The termination condition of binary tree traversal is obviously traversal to the leaf node, and each leaf node can be used as the left and right subtrees of the parent node recursive traversal, but the two subtrees have no child nodes, so inBelong to the“, we just need to save the values of the left and right subtrees and the current root node in the desired traversal order

  • Pay attention to

    • We’re going to look at traversing an empty tree, so we’re going to check if root is null, and if it is, we’re going to return an empty array

  • Code:

var preorderTraversal = function (root) {
  // We can write an internal function for recursion, because we already check whether root is null before recursion, so we can not write a recursive function to check whether root is null
  // If the tree is not empty, it will be judged again
  if (root === null) return []
  let ans = [root.val]
  if(root.left) ans = ans.concat(... preorderTraversal(root.left))if(root.right) ans = ans.concat(... preorderTraversal(root.right))return ans
}
Copy the code

Iterative method

  • Answer:
    • In the traversal process of binary tree, the main solution is to keep the record of the parent node information in the traversal process, and to traverse in the correct way.
    • To solve this problem using an iterative approach means that you need something that retains information about a tree that is not fully traversed, and here we can solve this problem using a stack
    • Because of the order of the front-order traversal, the root node value is saved first, and then the left and right subtrees are saved on the stack. Because of the first-in-last-out order of the stack, we need to push the right subtree first, then the left subtree. The order is as follows
      • Save the root node to the stack
      • Start traversal – exit the stack, save the value of the exit node into the result – judge whether the left subtree of the stack node exists, then push the left subtree onto the stack – judge whether the right subtree of the stack node exists, then push the right subtree onto the stack – repeat the traversal process until the stack is empty and the traversal ends
  • Code:
var preorderTraversal = function (root) {
  let ans = []
  if (root) {
    let stack = [root]
    while (stack.length > 0) {
      let tmp = stack.pop()
      ans.push(tmp.val)
      if (tmp.right) stack.push(tmp.right)
      if (tmp.left) stack.push(tmp.left)
    }
  }

  return ans
}
Copy the code

1. Middle order traversal of binary tree

94. Middle order traversal of binary trees

describe

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

Example:

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

The recursive method

  • Answer:

    • Like other traversals, we can split tree traversal into left -> middle -> right traversal order of middle traversal, get the value of the root node, and then traverse the right subtree.
    • So we just write a recursive function that recursively traverses the left subtree, then adds the result of the recursion to the root node and the result of the recursion of the right subtree
  • Code:
var inorderTraversal = function (root) {
  let ans = []
  if (root === null) {
    return ans
  }
  if (root.left) ans = inorderTraversal(root.left)
  ans = [...ans, root.val]
  if (root.right) ans = ans.concat(inorderTraversal(root.right))
  return ans
}
Copy the code

Iterative method

  • Answer:

    • Just like the previous iteration to solve the tree traversal problem, we need to use an external data structure to store the parent node during the tree traversal.

    • By analyzing the preorder traversal procedures, can be found, we are always the most on the left to start from a tree traversal, when the left no nodes, began to superior search, the process of return to the superior, can save the results down at the same time, and then judge whether the current node has the right subtree, if any, is also to traverse the corresponding.

    • Therefore, we can carry out middle-order traversal of binary tree by the following method

      • A stack is used to store node information. Using a pointerpStart by pointing to the root of the entire tree.
      • Since middle-order traversal starts from the left subtree, we want to find the leftmost node. Therefore a pointerpWe’re going to keep going to the left until there’s no left node, but as the pointer moves, we’re going to use a stack to keep the nodes that we’re passing by, because we haven’t walked through them yet, and we’re going to have to move the pointer after we’ve walked through the left nodepThe ability to go back to the parent node and iterate over the other nodes.
      • whenpIs null, means that the stack already on the path to the leftmost node node saved (also contains the leftmost node) at this time we according to the traverse sequence should be stack stack elements (that is, the most left node) out of the stack, and to save their values to iterate through the result of right of a stack pointer to a node at the same time, when the next cycle, If the right node exists, the same method will be used to traverse its right subtree, if it does not exist, then the stack will be removed, and the operation will be repeated.
  • Code:
var inorderTraversal = function (root) {
  let stack = []
  let ans = []
  let p = root
  while (p || stack.length) {
    if(p ! = =null) {
      stack.push(p)
      p = p.left
    } else {
      p = stack.pop()
      ans.push(p.val)
      p = p.right
    }
  }
  return ans
}
Copy the code