“This article has participated in the good article call order activity, click to see: back end, big front end double track submission, 20,000 yuan prize pool for you to challenge!”

Preface 🏕 ️

In our daily life, we see trees all the time. For example, when walking in the street, there are rows of trees. So, what are the applications of trees in the front end?

In fact, when the front end writes pages, each page has its own DOM tree, CSSOM tree, and so on. In addition, when we write cascading selectors, it’s one layer on top of the other, just like a tree.

In the following article, we will explain some basic operations of the tree data structure and its application in the front end.

Let’s learn about ba ~🧐

🌲 What is a tree?

Tree is an abstract model with hierarchical data function.
Commonly used trees for front-end work include:DOMTrees, cascading selection, tree space… .
JSThere is no tree, but you can use itObject 和 ArrayBuild a tree.
Common tree operations: depth/breadth first traversal, first in order traversal.

🌴 2. Deep/breadth traversal first

1. Depth-first traversal

(1) Definition

Depth-first traversal, that is, search the branches of the tree as deep as possible.

(2) formula

Access the root node.
For the root nodechildrenDo a depth-first traversal one by one.

(3) Code implementation

Next, we use JS to implement the depth-first traversal of the tree. The specific code is as follows:

const tree = {
    val:'a'.children:[
        {
            val:'b'.children:[
                {
                    val:'d'.children:[]
                },
                {
                    val:'e'.children[]}]}, {val:'c'.children:[
                {
                    val:'f'.children:[]
                },
                {
                    val:'a'.children:[]}]}const dfs = (root) = > {
    console.log(root.val);
    // Use recursion
    root.children.forEach(dfs);
}

A b d e c f a */
Copy the code

From the above code, we can know that we first define a tree tree, and then use recursive method to traverse the Children of the tree one by one, and finally get the print result of abDECFA.

What would make this order a little bit easier to understand?

So what we talked about up here is that the tree is traversing deeper. So in our tree, we have to go through the first level before we can go through the second level. The first layer of content has many layers, so let’s first go through the depth of it, wait until the first layer of the depth of traversal is finished, then we start to traverse the second layer of traversal.

So, let’s take a look at it first, the top is A, then the first layer, the first layer has BDE, then the second layer, the second layer has CFA. Therefore, the final order is abdecFA.

2. Breadth first traversal

(1) Definition

Breadth-first traversal, where the node closest to the root node is accessed first.

(2) formula

Create a queue.
Take the team leader out of line and visit.
Head of the teamchildrenJoin the team one by one.
Repeat steps 2 and 3 until the queue is empty.

(3) Code implementation

The next step is to use JS to implement the breadth first traversal of the tree. The specific code is as follows:

const tree = {
    val:'a'.children:[
        {
            val:'b'.children:[
                {
                    val:'d'.children:[]
                },
                {
                    val:'e'.children[]}]}, {val:'c'.children:[
                {
                    val:'f'.children:[]
                },
                {
                    val:'a'.children:[]}]}const bfs = (root) = > {
    // Create a new queue and put the root node in the queue first
    const q = [root];
    while(q.length > 0) {// Keep going out and visiting
        const n = q.shift();
        // Visit while going out of line
        console.log(n.val);
        // Put the children in the queue one by one and back into the queue
        n.children.forEach(child= > {
            q.push(child);
        });
    }
}

bfs(tree);

A b c d e f a */
Copy the code

🌱 iii. Binary tree

1, define,

For a binary tree, each node in the tree can have at most two child nodes.
JSThere is no binary tree, but objects are usually usedObjectSimulate binary trees.

2, binary tree first/middle/after order traversal

(1) Preorder traversal

Access the root node.
Preorder traversal of the left subtree of the root node.
Preorder traversal of the right subtree of the root node.

(2) in order traversal

Perform in-order traversal of the left subtree of the root node.
Access the root node.
Perform in-order traversal of the right subtree of the root node.

(3) Sequential traversal

A post-order traversal of the left subtree of the root node is performed.
A postorder traversal of the right subtree of the root node is performed.
Access the root node.

3, JS implementation first in the order after three traversal

Let’s use code to implement these three traversals of the binary tree. Here we go

(1) JS implementation of binary tree preorder traversal

For a binary tree preorder traversal, the root node is accessed first, then the left subtree is accessed, and finally the right subtree is accessed. Let’s implement preorder traversal in two ways, the first is a recursive version and the second is a non-recursive version.

First define a tree:

const bt = {
    val:1.left: {val:2.left: {val:4.left:null.right:null
        },
        right: {val:5.left:null.right:null}},right: {val:3.left: {val:6.left:null.right:null
        },
        right: {val:7.left:null.right:null}}}Copy the code

Recursive version implementation:

// The recursive version is implemented
const preOrder1 = (root) = > {
    if(! root){return;
    }
    console.log(root.val);
    preOrder1(root.left);
    preOrder1(root.right);
}

preOrder1(bt);
/** print result: 1 2 4 5 3 6 7 */
Copy the code

Non-recursive version implementation:

// Non-recursive version
/** * create a stack to simulate the function call stack; * 2. For preorder traversal, first remove the root node and then traverse the left subtree and the right subtree; * 3. According to the advanced and out characteristics of the stack, first put the right subtree into the stack, and then put the left subtree into the stack, one by one. * /
const preOrder2 = (root) = > {
    if(! root){return;
    }
    // Create a new stack to represent the call stack of the function
    const stack = [root];
    // console.log(stack)
    while(stack.length){
        // Pop the root node off the stack
        const n = stack.pop();
        console.log(n.val);
        if(n.right){
            stack.push(n.right);
        }
        if(n.left){
            stack.push(n.left);
        }

    }
}

preOrder2(bt);
/** print result: 1 2 4 5 3 6 7 */
Copy the code

(2) JS implementation of binary tree in order traversal

In order traversal of binary tree, the left subtree is first accessed, then the root node is accessed, and finally the right subtree is accessed. Let’s implement in-order traversal in two ways, the first is a recursive version and the second is a non-recursive version.

Similarly, let’s define a tree first:

const bt = {
    val:1.left: {val:2.left: {val:4.left:null.right:null
        },
        right: {val:5.left:null.right:null}},right: {val:3.left: {val:6.left:null.right:null
        },
        right: {val:7.left:null.right:null}}}Copy the code

Recursive version implementation:

// The recursive version is implemented
const inOrder1 = (root) = > {
    if(! root){return;
    }
    inOrder(root.left);
    console.log(root.val);
    inOrder(root.right);
}

inOrder1(bt);
/** print result: 4 2 5 1 6 3 7 */
Copy the code

Non-recursive version implementation:

// Non-recursive version
/** * create a stack to simulate the function call stack; * 2. For in-order traversal, all left subtrees need to be thrown into the stack; 3. When the traversal is complete, pop up the last node and access it; 4. After visiting the left node, you need to visit the right node; * /
const inOrder2 = (root) = > {
    if(! root){return;
    }
    let p = root;
    const stack = [];
    while(p || stack.length){
        while(p){
            / / advanced stack
            stack.push(p);
            // Continue to refer to the left subtree after the stack
            p = p.left;
        }
        // Pop the last one
        const n = stack.pop();
        console.log(n.val);
        p = n.right;
    }
    
}

inOrder2(bt);
/** print result: 4 2 5 1 6 3 7 */
Copy the code

(3) JS implementation of binary tree after order traversal

In order to traverse a binary tree, the left subtree is first accessed, then the right subtree is accessed, and finally the root node is accessed. Let’s do this in two ways, the first is a recursive version and the second is a non-recursive version.

First, once again, let’s define a tree:

const bt = {
    val:1.left: {val:2.left: {val:4.left:null.right:null
        },
        right: {val:5.left:null.right:null}},right: {val:3.left: {val:6.left:null.right:null
        },
        right: {val:7.left:null.right:null}}}Copy the code

Recursive version implementation:

// The recursive version is implemented
const postOrder1 = (root) = > {
    if(! root){return;
    }
    postOrder1(root.left);
    postOrder1(root.right);
    console.log(root.val);
}

preOrder1(bt);
/** print result: 1 2 4 5 3 6 7 */
Copy the code

Non-recursive version implementation:

// Non-recursive version
/** * create stack; * 2. Put the left subtree and the right subtree into the stack * 3. Create a reverse stack outputStack, first put the root tree into, and then one by one into the right subtree, after all put the left subtree */
const postOrder2 = (root) = > {
    if(! root){return;
    }
    // Output the stack in reverse order, put the root in the order of right and left, and then one by one
    const outputStack = [];
    // Put the left subtree first, and then the right subtree
    const stack = [root];
    while(stack.length){
        const n = stack.pop();
        outputStack.push(n);
        if(n.left){
            stack.push(n.left);
        }
        if(n.right){ stack.push(n.right); }}while(outputStack.length){
        const n = outputStack.pop();
        console.log(n.val);
    }
}
preOrder2(bt);
/** print result: 1 2 4 5 3 6 7 */
Copy the code

(4) Summary

After looking at the above code implementation, let’s conclude. Why show the recursive and non-recursive versions here?

In fact, recursive traversal is very common in our daily development. But think about it, sometimes our business logic may be very complex, and the amount of data that the front end receives from the back end is relatively large. At this time, if you use the recursive version of the processing, the algorithm complexity will be relatively high.

So we have a non-recursive version of the implementation, the non-recursive version of the implementation, which is designed to trade space for time, to reduce the time complexity of the code.

☘️ 4, Leetcode classic topic analysis

Next, we quote some classic Leetcode algorithms to consolidate our knowledge of trees and binary trees.

1, leetCode104 binary tree maximum depth (simple)

(1)

Attached is a link to the title: LeetCode104 Maximum depth of a binary tree

Given a binary tree, find its maximum depth.

The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.

Note: A leaf node is a node with no child nodes.

Examples of input and output:

The input: Given a binary tree[3,9,20, null, null, 15, 7]
Output: 3

(2)

To find the maximum depth, consider using depth-first traversal.
In the depth-first traversal process, the hierarchy of each node is recorded to find the largest hierarchy.

(3) Problem solving steps

Create a new variable and record the maximum depth.
Depth-first traverses the tree and records the hierarchy of each node, constantly refreshing the variable for the maximum depth.
Returns the variable with the maximum depth at the end of the traversal.

(4) Code implementation

/ * * *@param {TreeNode} root
 * @return {number}* /
let maxDepth = function(root) {
    let res = 0;
    const dfs = (n, l) = > {
        if(! n){return;
        }
        if(! n.left && ! n.right){ res =Math.max(res, l);
        }
        dfs(n.left, l + 1);
        dfs(n.right, l + 1);
    }
    dfs(root, 1);
    return res;
}
Copy the code

2, leetCode111 binary tree minimum depth (simple)

(1)

Attached is a link to the title: LeetCode111 Minimum depth of binary trees

Given a binary tree, find its minimum depth.

Minimum depth is the number of nodes on the shortest path from the root node to the nearest leaf node.

A leaf node is a node with no child nodes.

Examples of input and output:

The input: root = [3,9,20, null, null, 15, 7]
Output: 2

(2)

To find the minimum depth, consider using breadth-first traversal.
During breadth-first traversal, when a leaf node is encountered, the traversal stops and returns to the node level.

(3) Problem solving steps

Breadth first traverses the entire tree and records the hierarchy of each node.
When a leaf node is encountered, return to the node level and stop traversal.

(4) Code implementation

/ * * *@param {TreeNode} root
 * @return {number}* /

let minDepth = function(root){
    if(! root){return 0;
    }

    const q = [[root, 1]].while(q.length){
        const [n, l] = q.shift();

        if(! n.left && ! n.right){return l;
        }
        
        if(n.left){
            q.push([n.left, l + 1]);
        }
        if(n.right){
            q.push([n.right, l + 1]); }}}Copy the code

3. Sequence traversal of LeetCode102 binary tree (medium)

(1)

Attached is a link to the title: Sequence traversal of leetCode102 binary tree

Given a binary tree, you are asked to return the values of the nodes it traverses sequentially. (that is, access all nodes layer by layer, from left to right).

Examples of input and output:

Input: binary tree: [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Output:
```
[[3],
  [9.20],
  [15.7]]Copy the code
```

(2)

The sequential traversal order is breadth first traversal.
However, you need to keep track of the current node hierarchy as you iterate, so you can add it to different arrays.

(3) Problem solving steps

Breadth first traversal of the binary tree.
As you iterate, you record the hierarchy of each node and add it to a different array.

(4) Code implementation

/ * * *@param {TreeNode} root
 * @return {number[][]}* /
/ / method
let levelOrder1 = function(root) {
    if(! root){return [];
    }
    const q = [[root, 0]].const res = [];
    while(q.length){
        const [n, level] = q.shift();
        if(! res[level]){// Create an array when there is no array in that hierarchy
            res.push([n.val]);
        }else{
            // Put the values directly into the array
            res[level].push(n.val);
        }
        if(n.left){
            q.push([n.left, level + 1]);
        }
        if(n.right){
            q.push([n.right, level + 1]); }}return res;
};

/ / method 2
let levelOrder2 = function(root){
    if(! root){return [];
    }
    const q = [root];
    const res = [];
    while(q.length){
        let len = q.length;
        res.push([]);
        while(len--){
            const n = q.shift();
            res[res.length - 1].push(n.val);
            if(n.left){
                q.push(n.left);
            }
            if(n.right){ q.push(n.right); }}}return res;
}
Copy the code

4, LeetCode94 binary tree in order traversal (simple)

(1)

Attached is a link to the title: LeetCode94 in order traversal of binary trees

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

Examples of input and output:

The input: root = [1, null, 2, 3]
The output: 31 [1]

(2) How to solve the problem && how to solve the problem

The idea and procedure of solving the problem here are similar to the sequence traversal above, so I won’t explain it any more. Let’s look at the code implementation directly.

(3) Code implementation

/ * * *@param {TreeNode} root
 * @return {number[]}* /
// Iterate over the version
 let inorderTraversal1 = function(root) {
    const res = [];
    const rec = (n) = > {
        if(! n){return;
        }
        rec(n.left);
        rec(n.val);
        rec(n.right);
    }
    rec(root);
    return res;
};

// Iterative version -- stack method
let inorderTraversal2 = function(root){
    const res = [];
    const stack = [];
    let p = root;
    while(stack.length || p){
        while(p){
            stack.push(p);
            p = p.left;
        }
        const n = stack.pop();
        res.push(n.val);
        p = n.right;
    }
    return res;
}

inorderTraversal1(root);
inorderTraversal2(root);
Copy the code

5, LeetCode112 path sum (simple)

(1)

Attached is a title link: LeetCODE112 Path sum

You are given the root node of the binary tree and an integer targetSum representing the sum of the targets. Determine if there is a path from the root node to the leaf node in the tree where the values of all nodes add up to the target and the targetSum.

A leaf node is a node that has no children.

Examples of input and output:

The input: root13,4,7,2 = [5,4,8,11, null, null, null, null, 1].targetSum = 22
Output: true,

(2)

During depth-first traversal, record the sum of the values of the nodes in the current path.
At the leaf node, determine whether the sum of node values for the current path is equal to the target value.

(3) Problem solving steps

The depth-first traversal of the binary tree determines whether the sum of the nodes in the current path is equal to the target value at the leaf node. If yes, true is returned.
At the end of the traversal, false is returned if there are no matches.

(4) Code implementation

/ * * *@param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}* /
/ / the recursive method
let hasPathSum = function(root, targetSum) {
    if(! root){return false;
    }

    let res = false;

    const dfs = (n, s) = > {
        if(! n.left && ! n.right && s === targetSum){ res =true;
        }
        if(n.left){
            dfs(n.left, s + n.left.val);
        }
        if(n.right){
            dfs(n.right, s + n.right.val);
        }
    }
    dfs(root, root.val);
    return res;
};
Copy the code

6. Leetcode129 Find the sum of numbers from root node to leaf node (medium)

(1)

Add the title link: Leetcode129 find the sum of root to leaf digits

Given the root node of a binary tree, root, each node in the tree contains a number between 0 and 9.

Each path from the root to the leaf represents a number:

For example, the path 1 -> 2 -> 3 from the root node to the leaf node indicates the number 123.

Calculates the sum of all the numbers generated from the root node to the leaf node.

Leaf nodes are nodes that have no child nodes.

Examples of input and output:

Input: root = [1,2,3]
Output: 25
explain:
- The path 1->2 from the root to the leaf node represents the number 12
- The path 1->3 from root to leaf indicates the number 13
- So the sum of the numbers is equal to 12 + 13 = 25

(2)

During a depth-first walk, the value of the node in front of the current path is recorded.
At the leaf node, the current path value is calculated.

(3) Problem solving steps

The depth-first traversal of the binary tree ends at the leaf node of each tree.
At the end of the traversal, return all path values.

(4) Code implementation

/ * * *@param {TreeNode} root
 * @return {number}* /
 var sumNumbers = function(root) {
    // Depth-first traversal processing
    
    const dfs = (n, preNum) = > {

        if(! n){return 0;
        }

        const sum = preNum * 10 + n.val;
        if(! n.left && ! n.right){return sum;
        }else{
            returndfs(n.left, sum) + dfs(n.right, sum); }}return dfs(root, 0);
};
Copy the code

🎄 5. Front end and tree: Traverse all the values of the JSON nodes

1. Chatter

Sometimes the data passed from the back end may not be very friendly, it may be a string of objects and arrays, and when the front end gets the data, it needs to deal with it a little bit.

Therefore, we can iterate through all the node values in the JSON with depth-first traversal.

Here’s an example

2. Code implementation

(1) Manufacturing data

Let’s say we have a string of JSON data in mind. The code looks like this:

const json = {
    a: {b: {c:1}},d: [1.2]}Copy the code

(2) Traversal node values

Next, we iterate through the values of all the nodes in the JSON using a depth-first traversal. The specific implementation code is as follows:

const dfs = (n, path) = > {
    console.log(n, path);
    Object.keys(n).forEach(k= > {
        dfs(n[k], path.concat(k));
    });
};

dfs(json, []);
Copy the code

(3) Print the results

The final print result is as follows:

{ a: { b: { c: 1}},d: [ 1.2]} {[]b: { c: 1}} ['a' ]
{ c: 1 } [ 'a'.'b' ]
1 [ 'a'.'b'.'c' ]
[ 1.2 ] [ 'd' ]
1 [ 'd'.'0' ]
2 [ 'd'.'1' ]
Copy the code

If you look at the print above, you can see that the data is traversed one by one by depth-first traversal. Therefore, for the tree data structure, in the front of the frequency is also high ~~

🏡 Conclusion

Through the study above, we understand two kinds of tree traversal: depth-first traversal and breadth-first traversal. At the same time, there is a special kind of tree, the binary tree. Binomial trees are basically a big part of the interview. For binary tree, it is necessary to understand its three kinds of traversal: first order, middle order and post order traversal, and to master the differences between these three and the common application scenarios.

So much for the use of trees in the front end! Hope to help you ~

If you have any questions or articles are wrong, please add my wechat questions in the comment area or the background of the public account

🐣 Easter Eggs One More Thing

Phase to recommend

Stack 👉 stack in the front end of the application, by the way to understand the deep copy and shallow copy!

Queue 👉 details the application of queue in the front end, deep profile JS Eventloop Eventloop, and then understand the micro task and macro task

List 👉 detailed list in front of the application, the way to understand the prototype and prototype chain!

Dictionaries and collections 👉 Do you know ES6’s Set and Map? Learn about collections and dictionaries in front end applications

Dynamic rules and divide and conquer algorithm 👉 to understand the sum of the divide and conquer dynamic rules algorithm in front of the application

Greedy algorithm and backtracking algorithm 👉 to understand the greedy algorithm and backtracking algorithm in front of the application

Set pieces

Pay attention to the public number Monday research office, the first time to pay attention to learning dry goods, more selected columns for you to unlock ~

If this article is useful to you, make sure you leave footprints before you go

That’s all for this article! See you next time! 👋 👋 👋

Learn about the application of the tree 🌳 in the front end and grasp the lifeline of the tree in the data structure

Preface 🏕 ️

🌲 What is a tree?

🌴 2. Deep/breadth traversal first

1. Depth-first traversal

(1) Definition

(2) formula

(3) Code implementation

2. Breadth first traversal

(1) Definition

(2) formula

(3) Code implementation

🌱 iii. Binary tree

1, define,

2, binary tree first/middle/after order traversal

(1) Preorder traversal

(2) in order traversal

(3) Sequential traversal

3, JS implementation first in the order after three traversal

(1) JS implementation of binary tree preorder traversal

(2) JS implementation of binary tree in order traversal

(3) JS implementation of binary tree after order traversal

(4) Summary

☘️ 4, Leetcode classic topic analysis

1, leetCode104 binary tree maximum depth (simple)

2, leetCode111 binary tree minimum depth (simple)

3. Sequence traversal of LeetCode102 binary tree (medium)

4, LeetCode94 binary tree in order traversal (simple)

5, LeetCode112 path sum (simple)

6. Leetcode129 Find the sum of numbers from root node to leaf node (medium)

🎄 5. Front end and tree: Traverse all the values of the JSON nodes

1. Chatter

2. Code implementation

(1) Manufacturing data

(2) Traversal node values

(3) Print the results

🏡 Conclusion

🐣 Easter Eggs One More Thing

Phase to recommend

Set pieces

Related Posts

Koa2 practice for Node

Tinymce – The first rich text editor in the universe? [1]

The backslash of the epic drama