“This is the 9th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

For basic concepts and a primer on binary trees, see my primer on binary trees for front-end developers in this article

Today, we mainly talk about the binary tree before traversal, middle traversal, and after the order traversal.

example

Let’s take an example: we have a binary tree, and let’s talk about the results of three traversals

A B D E C F G

D B E A F C G

D E B F G C A

concept

To explain why this is the case, let’s look at the definitions of these three traversals:

Pre-order traversal: first visits the root, then traverses the left subtree, and finally traverses the right subtree.

Middle-order traversal: Traverses the left subtree first, then the root, and finally the right subtree.

Back-order traversal: traverses the left subtree first, then the right subtree, and finally the root.

Next, let’s start with a simple example

The results of the three types of traversal in this diagram are analyzed in conjunction with the concepts we just introduced

A, B, C

Middle order traversal: B A C

After traversal: B C A

Simply put, A is our root node, pre-order traversal means A comes first, middle-order traversal means A comes in the middle, and post-order traversal means A comes in the last.

At this point, if you understand it, then you’re done understanding recursion. If you don’t understand it, you are advised to start over again.

recursive

What’s the difference between the three traversals when B has children?

The former sequence traversal

Let’s look at the pre-order traversal, the pre-order traversal is A, B, and C, and if B has children, that means we have to split the data into A => (B subtree) => C.

And then we’re going to construct the B subtree, and we’re back up here

This is going to work, right? It’s going to be B, D, E

Plus A and C from the previous step, so it’s A, B, D, E, and C.

In the sequence traversal

If B has A child node, it means that we need to split the data into (B subtree) => A => C.

The middle result of the B subtree is D, B, and E

Plus A and C from the previous step, so it’s D, B, E, A and C.

After the sequence traversal

And finally, post-order traversal, post-order traversal comes in the order B, C, A, if B has children, that means we have to split the data into (B subtree) => C => A.

B subtree is D, E, B

Plus A and C from the previous step, so it’s D, E, B, C, A.

To understand this step, go back to the title of the three traversal results, did not understand the welcome comment section DISs I ha ha, I continue to improve.

implementation

The former sequence traversal

/** * 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[]}* /
function postorderTraversal(root) {
    return root ? getNextNode(root) : [];
};


function getNextNode(node, result = []) {
    result.push(node.val); // Forward traversal, push the current node first
    node.left && getNextNode(node.left, result);
    node.right && getNextNode(node.right, result);
    return result;
};
Copy the code

In the sequence traversal

/** * 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[]}* /
function postorderTraversal(root) {
    return root ? getNextNode(root) : [];
};


function getNextNode(node, result = []) {
    node.left && getNextNode(node.left, result);
    result.push(node.val); // In order traversal, push the current node in the middle
    node.right && getNextNode(node.right, result);
    return result;
};
Copy the code

After the sequence traversal

/** * 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[]}* /
function postorderTraversal(root) {
    return root ? getNextNode(root) : [];
};


function getNextNode(node, result = []) {
    node.left && getNextNode(node.left, result);
    node.right && getNextNode(node.right, result);
    result.push(node.val); // After traversal, push the current node at the end
    return result;
};
Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.