Review past

  • Array reworking +6 front-end algorithms interview frequency problem solving | brush problem punching
  • Linked list +6 front-end algorithms interview high-frequency problem solving | brush problem punching

Tree related noun popular science

  • The root node
  • A leaf node
  • The parent node
  • Child nodes
  • Brother nodes
  • highly
  • The depth of the
  • layer

A is the root node. C, D, F, and G are leaf nodes. A is the parent of B and E. B and E are children of A. B and E are sibling nodes.

Height, depth and layer are shown in the figure above.

For easy memorization, height means looking up, depth means looking down.

Different from height and depth, floors are similar to buildings in Inception. Buildings are counted from the first floor. In Inception, buildings are inverted and start from the top down.

That’s the end of the tree basics, but if you’d like to know more, please take a step back to my column, “Tree Pros,” which specializes in trees

Open the brush problem

  • LeetCode problem solving warehouse in front canteen

At the beginning of the year, a flag was set that the warehouse would write 100 front-end interview high-frequency questions in 2021, and the progress has been 50% completed.

If you are going to brush or are currently brushing LeetCode, join the front canteen and have a good time.

Now we will start our happy journey of brushing questions. I sorted out 8 high-frequency LeetCode linked list questions and their solutions as follows.

01 Middle order traversal of binary tree

The original link

Middle-order traversal: Print the left subtree of the current node first, then the current node, and finally the right subtree (CBDAFEG) of the current node, as shown in the figure above.

const inorderTraversal = function(root) {
    const result = [];
    function pushRoot(root) {
        if(root ! = =null) {
            if(root.left ! = =null) {
                pushRoot(root.left);
            }
            result.push(root.val);
            if(root.right ! = =null) { 
                pushRoot(root.right);
            }
        }
    }
    pushRoot(root);
    return result;
};
Copy the code
  • Time complexity: O(n)
  • Space complexity: O(n)

02 Antecedent traversal of binary trees

The original link

Sequential traversal: Prints the current node first, then the left subtree of the current node, and finally the right subtree (ABCDEFG) of the current node, as shown in the figure above.

const preorderTraversal = function(root) {
    const result = [];
    function pushRoot(node){
        if(node ! = =null) {
            result.push(node.val);
            if(node.left ! = =null){ 
                pushRoot(node.left);
            }
            if(node.right ! = =null) {
                pushRoot(node.right);
            } 
        }
    }
    pushRoot(root);
    return result;
};
Copy the code
  • Time complexity: O(n)
  • Space complexity: O(n)

Posterior order traversal of binary tree

The original link

Back-order traversal: First print the left subtree of the current node, then the right subtree of the current node, and finally print the current node (CDBFGEA), as shown in the figure above.

const postorderTraversal = function(root) {
    const result = [];
    function pushRoot(node) {
        if(node ! = =null) {
            if(node.left ! = =null) {
                pushRoot(node.left);
            }
            if(node.right ! = =null) {
                pushRoot(node.right);
            } 
            result.push(node.val);
        }
    }
    pushRoot(root);
    return result;
};
Copy the code
  • Time complexity: O(n)
  • Space complexity: O(n)

04 Same tree

The original link

Depth-first search DFS

  1. If both binary trees are empty, they both return true.
  2. If one of the two binary trees is empty, they return false differently.
  3. If neither binary tree is empty, check whether the root node is the same. If not, return false.
  4. If the root nodes of two binary trees are the same, the left and right subtrees are recursively judged to be the same.
const isSameTree = function(p, q) {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;
    if(p.val ! == q.val)return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};
Copy the code
  • Time complexity: O(min(m, n))
  • Space complexity: O(min(m, n))

Symmetric binary trees

The original link

recursive

Just to be clear, symmetry is when two trees have the same root and

  • The left subtree of the first tree is mirrored by the right subtree of the second tree.
  • The right subtree of the first tree is mirrored by the left subtree of the second tree.
const isSymmetric = function(root) {
    if (root === null) return true
    return isEqual(root.left, root.right) // Compare the symmetry of left and right subtrees
};

const isEqual = function(left, right) {
    // Recursive termination condition
    if (left === null && right === null) return true / / symmetric
    if (left === null || right === null) return false / / asymmetry
    // Compare the root values of the left and right subtrees and whether the left and right subtrees are symmetric
    return left.val === right.val
        && isEqual(left.left, right.right)
        && isEqual(left.right, right.left)
}
Copy the code
  • Time complexity: O(n)
  • Space complexity: O(n)

06 Order traversal of binary tree

The original link

DFS depth-first traversal

Add nodes of each layer to the array of the corresponding layer according to the depth of the tree.

const levelOrder = function(root) {
    if(! root)return []
    const res = []
    dfs(root, 0, res)
    return res
};

const dfs = function(root, depth, res) {
    if(! root)return // Recursive termination condition
    if(! res[depth]) res[depth] = [] res[depth].push(root.val)// Store node values for each layer
    dfs(root.left, depth + 1, res) // drill down
    dfs(root.right, depth + 1, res)
}
Copy the code

BFS breadth-first traversal

Returns the corresponding result set according to the hierarchy.

  1. Boundary processing, initialize the queue and the array res that holds the results.
  2. The outer loop traverses the hierarchy, and the inner loop traverses the children of each layer.
  3. The traversal needs to record len of the current layer and arr of the node array of the current layer.
  4. Nodes are queued and stored in the node array of the current layer.
  5. If there are left and right child nodes, join the queue in turn and update len.
  6. The result, res, is returned.
const levelOrder = function(root) {
    if(! root)return []
    const queue = [root]
    const res = []
    while (queue.length > 0) {
      const arr = []
      let len = queue.length
      while (len) {
        let node = queue.shift()
        arr.push(node.val)
        if (node.left) queue.push(node.left)
        if (node.right) queue.push(node.right)
        len--
      }
      res.push(arr)
    }
    return res
};
Copy the code
  • Time complexity: O(n)
  • Space complexity: O(n)

07 Maximum depth of a binary tree

The original link

DFS depth-first search

Tree depth = maximum depth of left and right subtrees + 1

const maxDepth = function(root) {
    if(! root) {// Recursive termination condition
        return 0
    } else {
        const left = maxDepth(root.left)
        const right = maxDepth(root.right)
        return Math.max(left, right) + 1}};Copy the code
  • Time complexity: O(n)
  • Worst space complexity: O(height), height indicates the height of the binary tree

BFS breadth first search

Sequence traversal records tree depth.

Binary tree sequence traversal can refer to easily take down binary tree sequence traversal

const maxDepth = function(root) {
    let depth = 0
    if (root === null) {
        return depth
    }
    const queue = [root]
    while (queue.length) {
        let len = queue.length
        while (len--) {
            const cur = queue.shift()
            cur.left && queue.push(cur.left)
            cur.right && queue.push(cur.right)
        }
        depth++
    }
    return depth
};
Copy the code
  • Time complexity: O(n)
  • Space complexity: O(n)

08 Flipping the binary tree

The original link

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t flip a binary tree on a whiteboard, so roll over, egg fried rice.

Screenshots of the original tweet still exist today. LeetCode added this problem right after Max Howell teased it.

Knowing this question, can we also surpass the world-class giants? (Dog’s head saved)

Firstly, it is clear that the so-called binary tree flipping needs to meet the following two points:

  1. Its left and right subtrees are going to switch places.
  2. And all the subtrees or nodes inside the left and right subtrees are going to swap places.

recursive

  1. Starting at the root, the tree is recursively traversed.
  2. Start at the leaf node and flip.
  3. After the left and right subtrees have been flipped, switching the positions of the two subtrees completes the full flip.
const invertTree = function(root) {
    if (root === null) return null // Recursive termination condition
    invertTree(root.left)
    invertTree(root.right)
    const temp = root.left
    root.left = root.right
    root.right = temp
    return root
}
Copy the code
  • Time complexity: O(n)
  • Space complexity: O(n)

Of course, you can also reverse steps 2,3 above, that is, first switch the positions of the two subtrees and then flip them inside.

const invertTree = function(root) {
    if (root === null) return null // Recursive termination condition
    const temp = root.left
    root.left = root.right
    root.right = temp
    invertTree(root.left)
    invertTree(root.right)
    return root
}
Copy the code

BFS

Sequential traversal traverses the binary tree, flipping its left and right subtrees when the root node is out of the column. The left and right child nodes are then added to the column so they can be flipped at the next level.

The sequence traversal of binary tree can refer to the solution above.

const invertTree = (root) = > {
  if (root == null) return null;
  const queue = [root];
  while (queue.length) {
    const cur = queue.shift();
    [cur.left, cur.right] = [cur.right, cur.left];
    if (cur.left) queue.push(cur.left);
    if (cur.right) queue.push(cur.right);
  }
  return root;
}
Copy the code

Write in the last

Give me a “like” if you think you’ve learned anything from reading this. If you have any questions, thoughts or feelings during the reading, please leave a comment below to communicate with me.

Communication creates value, sharing brings happiness. You are also welcome to share with other students in need, altruism is the best self-interest.

  • This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign