Briefly describe binomial trees

A binary tree is a tree with at most two branches per node. Traversal mode can be traversed layer by layer from top to bottom, visiting the node nearest to the root first, known as breadth-first traversal, or starting from the root node and traversing to the farthest node, known as depth-first traversal. In addition, traversal can be divided into pre-order traversal, middle-order traversal and back-order traversal according to the visit sequence of the root node.

Instead, just remember how to access the root node.

• Access the node closest to the root: breadth-first traversal

• Accessing the node farthest from the root: depth-first traversal

  • Access the root node first, then the left and right subtrees: pre-order traversal
  • Visit the root node in the middle, that is, the left subtree, the root node, and the right subtree first: middle order traversal
  • Last access to the root node: first access to the left and right subtrees, then access the root node: subsequent traversal

So, after sorting out the order of access, it is not difficult to understand the traversal and reconstruction of binary trees.

I found that except for the binary tree traversal, the rest of the questions were written recursively. Because it’s probably too easy to recurse and do basic node access, you can just switch places. So let’s talk about recursion first.

Here is how to write depth-first traversal.

recursive

The former sequence traversal

Topic describes

Antecedent traversal of binary trees

The complete code

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number[]}* /

const traverse = (root, res) = > {
    if(! root)return null;
    
    // Preorder traversal position: around the root
    res.push(root.val);
    
    traverse(root.left, res);
    
    traverse(root.right, res);
}

var preorderTraversal = function(root) {
    let res = []
    traverse(root, res)
    return res;
};
Copy the code

In the sequence traversal

Topic describes

Middle order traversal of binary trees

The complete code

const traverse = (root, res) = > {
    if(! root)return null;
    traverse(root.left, res);
    
    // Order traversal position: left root right
    res.push(root.val);
    
    traverse(root.right, res);
}

var preorderTraversal = function(root) {
    let res = []
    traverse(root, res)
    return res;
};
Copy the code

After the sequence traversal

Topic describes

Backward traversal of a binary tree

As a rule of thumb, subsequent traversals should be done by moving res.push(root.val) to traverse(root.right, res).

The complete code

const traverse = (root, res) = > {
    if(! root)return null;
    traverse(root.left, res);
 
    traverse(root.right, res);
    
    // After traversal position: left and right root
    res.push(root.val);
}

var preorderTraversal = function(root) {
    let res = []
    traverse(root, res)
    return res;
};

Copy the code

The iteration

Iteration is written using a stack, and recursion can be seen as hiding the stack from us, but function calls are actually made through the stack. The access location is also determined by location.

Front-order traversal (first root, then left and right)

The complete code

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number[]}* /

var preorderTraversal = function(root) {
    let result = [];
    let stack = [];
    let cur = root;
    while(cur || stack.length){
        while(cur){
            // Put the current node (root node) into the result
            result.push(cur.val);

            // Push the current node onto the stack and traverse its left subtree, adding it to the stack in turn
            stack.push(cur);
            cur = cur.left;
        }
        
        // Push the right node onto the stack
        cur = stack.pop();
        cur = cur.right;
    }

    return res;
};
Copy the code

Steps and dismantling

• We need to define three variables: result, stack, and cur

  • let result = []Used to store results
  • let stack = []The extra stack is needed to change the order of access of nodes, so that the last order of exit from the stack is root left and right, so that the order of entry is root left and right.
  • let cur = rootFor access to the current node.

• Before traversing, we need to check that the root node of the tree passed in exists, and since the stack is always pushed, the loop stops when it is empty.

while(cur || stack.length){
    // ...
}
Copy the code

• It’s time to traverse!

  • If the currentcurIf yes, the root node exists firstresult, and then pushes the current node onto the stack, and pushes all the left nodes of the current node onto the stack

      while(cur || stack.length){
          while(cur){
              // The first time through the loop, cur = root, so push the root node directly to result first
              result.push(cur.val);
              
              // Push the current node onto the stack
              stack.push(cur);
              
              // Push all left nodes of the current node onto the stack
              cur = cur.left;
          }
          / /...
      }     
  Copy the code

  • At this point, the root node and its left subtree are pushed onto the stack, and then we go off the stack and look at the right subtree of the current node,

    while(cur || stack.length){
        / /...
        
        // When there is no left subtree, push the current node off the stack and view the right subtree of the current node. If there is, push the current node on the stack
        cur = stack.pop();
        cur = cur.right;
    }   
    Copy the code

Middle-order traversal (left-middle-right, middle-root traversal, left-first, right-last)

Actually understandable for binary tree, the root node and the left subtree is a poker into the stack and the stack elements one by one in the stack, at this time, the current out of the stack elements have no left subtree, itself is the root node of the tree and put it in the results, and then see if the element is right subtree, if not out of the stack, or to continue into the stack.

Steps and dismantling

• The root node and all nodes of the left subtree are pushed first

• Unstack the nodes one by one, and store the value of the current node into the result, look at the right subtree of the current node, if there is no node, continue to unstack, otherwise push it into the stack.

The complete code

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number[]}* /


var inorderTraversal = function(root) {
    let result = [];
    let stack = [];
    let cur = root;
    
    while(cur || stack.length){
        // Push the root node and all left subtrees onto the stack
        while(cur){
            stack.push(cur);
            cur = cur.left;
        }
        Add the current value to the result and check if the current node has a right subtree. If it does not, continue to unstack, if it does, push the right node to the stack. Dump stacks in left, root, and right order
        cur = stack.pop();
        
        result.push(cur.val);
        
        cur = cur.right;
    }
    return result;
};
Copy the code

Back-order traversal (left-right center, first left-right, last root node)

Subsequent traversal and writing is the same as the front, the only thing to note is need a variable to hold the previous node, because for a tree, the root and the left node is access to the first, and the result is we need the output sequence is first about node, after the root node, so we need to mark whether the node being visited.

var postorderTraversal = function(root) {
    let stack = [];
    let result = [];
    let prev = null;
    let cur = root;
    while(cur || stack.length){
    
    // Start from the root node and push it all the way to the left.
    while(cur){
        stack.push(cur);
        cur = cur.left;
    }
    
    // Get the current node
    cur = stack[stack.length - 1];
    
    // Check whether the right node exists and is not the previous node, indicating that the node has a right subtree and has not been traversed
    if(cur.right && cur.right ! = prev){ cur = cur.right; }else{
        // if the cur node has no right subtree and its right subtree has been traversed, the node can be traversed, thus exiting the stack and traversing it
        stack.pop();
        result.push(cur.val);
        prev = cur;
        cur = null; }}return result;
};
Copy the code

Iterative traversal summary

Iteration is very similar to recursion, except that the recursion is not difficult to write in the interview, and the interviewer will not ask, but the iteration is a little more difficult, but in fact it can be written easily by following these steps.

• Iteration requires figuring out the conditions for cyclic planting, an auxiliary stack, and an array to hold the results

let stack = [];
let result = [];
let cur = root;
while(cur || stack.length){
    // ...
}
Copy the code

• Figure out when result.push(cur.val) is executed, and subsequent traversals also need to save the previous node to determine whether the right subtree of that node has been accessed.

  • The former sequence traversal
  • In the sequence traversal

  let stack = [];
  let result = [];
  let cur = root;
  while(cur || stack.length){
      while(cur){
          // The position of the preceding traversal
          // result.push(cur.val);
  
          stack.push(cur);
          cur = cur.left;
      }
     cur = stsack.pop();
     // The position of the sequence traversal
     // result.push(cur.val);
     cur = cur.right;
  }
  Copy the code

  • Subsequent traversal

  let stack = [];
  let result = [];
  let prev = null;
  let cur = root;
  while(cur || stack.length){
      while(cur){
          stack.push(cur);
          cur = cur.left;
      }
     cur = stack[stack.length - 1]
     if(cur.right && cur.right ! = prev){ cur = cur.right; }else {
         stack.pop();
         // The position of the sequence traversal
         result.push(cur.val);
         prev = cur;
         cur = null; }}Copy the code

Complexity analysis

The complexity is the same for both iteration and recursion.

Time complexity: O(n)

Space complexity: O (h) H is the depth of the binary tree. The minimum value of depth h in the binary tree is log(n+1) and the maximum value is n