“This is the 16th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

background

Before I went to see vue-Router source code, I found the classic traversal framework of n-tree, in the source code to find algorithms such as data structures, in fact, it is not very easy (for me) because the source code itself is nested nested nested nested nested nested, infinite nesting children, there are a lot of technical details easy to trap, Some very classical data structures may not be recognized if you don’t see them at a glance, and the reason why it can be found and extracted in many codes is that it is an N-tree traversal because I have brushed some n-tree topics before this, and I have also learned about the n-tree traversal framework mentioned by Labuladong. So this article will take my family to have a look at the title of N-fork tree in Leetcode

After reading this article, you can try the following questions (rest assured that they are easy).

1. 559. The maximum depth of the N fork tree
2. 589. Antecedent traversal of N fork trees
3. 590. Post-order traversal of N fork trees
4. 429. Sequence traversal of N fork tree

N – tree traversal framework

So this is what’s called an n-tree traversal framework

const traverse = (root) = > {
  if (root === null) {
    return;
  }
  for (let i = 0; i < root.children.length; i++) { traverse(root.children[i]); }};Copy the code

Now it looks simple, but you can do a lot of things, like the definition of the pre-order position of the binary tree can be nested inside the framework, plus the pre-order position code is like this

const traverse = (root) = > {
  if (root === null) {
    return;
  }
  // Forward position
  for (let i = 0; i < root.children.length; i++) {
    traverse(root.children[i]);
  }
  // Back position
};
Copy the code

Let’s start with a classic image from front to back

The pre-order position should be easy to understand, and the post-order position is a return, where all the children are iterated, to exit the for loop

There may be family members who want to ask, but what about the middle order? In fact, there is no specific definition of the middle order position of an N-tree. The middle order definition of a binary tree is the order of the left root and the right, but it does not seem to be valid in an N-tree. There is only one pointer when the child node of an N-tree is empty, unlike the function of turning when the two child nodes of a binary tree are empty. Left subtree to right subtree (I certainly won’t say I can’t, manual dog head)

So going back to the front and the back, what’s the use of an n-fork tree getting those two positions? Is really like binary tree, sequence location before you can get the parent node to child nodes information, after the order to get the child nodes to return to parent node position information, in fact the two position also implied back and the thought of dynamic planning, top-down and top up the thinking, dynamic planning also have the problem of decomposition of ideas in there, When looking at the following leetcode problem analysis, you can set the above ideas to understand

589. Antecedent traversal of N fork trees

A simple question, appetizer, in fact, you just look at the front position of the train of thought has already made the majority, is traversing N fork tree is not on the line? It’s pretty simple, but there’s a little bit of a problem with keeping track of how we’re moving, and that’s pretty easy to solve, by putting an array outside of the traversal function. Here’s the code

var preorder = function (root) {
  let res = [];
  const traverse = (root) = > {
    if (root === null) {
      return;
    }
    res.push(root.val);
    for (let i = 0; i < root.children.length; i++) { traverse(root.children[i]); }}; traverse(root);return res;
};
Copy the code

Res = [] is where we store the path, and when we enter the node, we store the value(node value) once. We can actually solve this problem by using the idea of dynamic programming, which has to do with post-order positions, depending on the information returned by the subtree

var preorder = function (root) {
  if (root === null) {
    return [];
  }
  const currentVal = [];
  for (let i = 0; i < root.children.length; i++) { currentVal.push(... preorder(root.children[i])); }return [root.val, ...currentVal];
};
Copy the code

Of course, this is not necessary, it’s a waste of space, you’re creating an array every time you iterate, and you’re running out of memory

590. Post-order traversal of N fork trees

I don’t think we need to talk about post-order traversal at all. Ok, res.push(root.val); Just switch places

// ...
for (let i = 0; i < root.children.length; i++) {
  traverse(root.children[i]);
}
res.push(root.val);
// ...
Copy the code

Dynamic programming can also be used for back-order traversal, decomposing the problem, just returning the subtree of the subtree, right?

var postorder = function (root) {
  const traverse = (root) = > {
    if (root === null) {
      return;
    }
    const currentVal = [];
    for (let i = 0; i < root.children.length; i++) { currentVal.push(... traverse(root.children[i])); }return [...currentVal, root.val];
  };
  return traverse(root);
};
Copy the code

There are some things that are actually so magical, and recursion is such an interesting thing, that the simplest code does the most things, and understanding this concept of pre-order and post-order, a lot of binary tree problems are easy

559. The maximum depth of the N fork tree

The maximum depth of n-tree can also be used in our front-to-back-order position, first of the classical solution

var maxDepth = function (root) {
  if (root == null) {
    return 0;
  }
  let res = -1;
  const traverse = (root, depth) = > {
    if (root === null) {
      return;
    }
    res = Math.max(res, depth);
    for (let i = 0; i < root.children.length; i++) {
      traverse(root.children[i], depth + 1); }}; traverse(root,1);
  return res;
};
Copy the code

Look carefully, is it similar, is it familiar with the pre-order position, is it familiar with the external variable, small transfer of a parameter can easily record the maximum depth, of course, there is a more elegant solution, dynamic programming solution, and because it is the transfer of depth information, do not worry too much about the memory problem

var maxDepth = function (root) {
  if (root == null) {
    return 0;
  }
  let res = 0;
  for (let i = 0; i < root.children.length; i++) {
    res = Math.max(res, maxDepth(root.children[i]));
  }
  return 1 + res;
};
Copy the code

Notice one small detail, because of the for loop, the RES actually changes as the for loop traverses, by comparing the maximum depth of multiple subtrees to get the maximum depth of the current tree

N – tree sequence traversal

In fact, this part does not have much to do with vue-Router, because vue-Router uses recursive traversal. However, recursive iteration is already a commonplace topic, so it is necessary to understand the following sequence traversal of n-tree

Sequence traversal actually using the characteristics of the queue this kind of data structure, first in first out, after traversal a node to its child nodes of poker to the queue, so the next time the team will be able to guarantee the traversal sequence, if learn a sequence of binary tree traversal should be well understood (N fork sequence traversal of the tree and even than the simple binary tree), Let’s take a simple picture to understand the sequence traversal

The solution code is as follows

var levelOrder = function (root) {
  const nodes = [root];
  const res = [];
  while(nodes.length ! = =0) {
    node = nodes.shift();
    res.push(node.val);
    for (let i = 0; i < node.children.length; i++) { nodes.push(node.children[i]); }}return res;
};
Copy the code

But the above solution won’t pass Leetcode, because leetocde needs a data structure like this

[[1]./ / the first layer
  [3.2.4]./ / the second floor
  [5.6]];/ / the third floor
Copy the code

In fact, this requirement is also easy to solve, because the size (length) of the next layer is determined by the previous layer, and each traversal will only have one layer of nodes, because the nodes of the previous layer are out of the queue, so as long as the number of nodes of the current layer, you can get the array val of the current layer, modify the code as follows

// ...
const currentVal = [];
const currentLength = nodes.length;
for (let i = 0; i < currentLength; i++) {
  node = nodes.shift();
  currentVal.push(node.val);
  if(node.children ! = =null) {
    for (let j = 0; j < node.children.length; j++) {
      nodes.push(node.children[j]);
    }
  }
}
res.push(currentVal);
// ...
Copy the code

conclusion

N fork tree actually can still meet in the practical application, like a multi-level navigation lists, the routing list, are commonly used, but is the structure of the binary tree that standard is not very common, but many of the properties of binary tree and the algorithm can be applied to the N fork, in the tree and binary tree are easier to understand, but said nothing more practice is the most important, Go to Leetcode and solve similar problems