Tree of data Structures

Tree introduction

What is a tree?

An abstract model of hierarchical data
Common trees in front-end work include: DOM tree, cascading selection, tree controls…
There are no trees in JS, but you can build trees with Object and Array.
Common operations on trees: depth/width first traversal, middle first and order second traversal

What is depth/breadth first traversal?

Depth-first traversal: Search as deep a branch of the tree as possible
Breadth-first traversal: Visits the node closest to the root node first

Depth-first traversal algorithm solution

Accessing the root node
Children of root node are traversed depth-first one by one

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

dfs(tree);
// Print: a b D e c f g
Copy the code

Breadth-first traversal algorithm solution

Create a queue and queue the root node
Take the team leader out of the team and visit
Put the children in the team one by one
Repeat steps 2 and 3 until the queue is empty

const tree = {
    val: 'a'.children: [{val: 'b'.children: [{val: 'd'.children: []}, {val: 'e'.children[],}],}, {val: 'c'.children: [{val: 'f'.children: []}, {val: 'g'.children: [],}],}],};/ / the recursive method
const bfs = (root) = >{
    let q = [root];
    while(q.length > 0) {const n = q.shift();
        console.log(n.val);
        n.children.forEach(item= >{
            q.push(item);
        })
    }
}

bfs(tree);
// Print: abcdefg
Copy the code

What is a binary tree

Each node in the tree can have a maximum of two child nodes
Object is commonly used to simulate binary trees in JS

const binaryTree = {
    val : 1.left: {val : 2.left : null.right: null
    },
    right: {val:3.left:null.right:null}}Copy the code

Sequential traversal method (root left and right)

Accessing the root node
Preemptive traversal of the left subtree of the root node
Preemptive traversal of the right subtree of the root node

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,}}};// Recursive method
const preorder = (root) = >{
    if(! root){return;
    }
    console.log(root.val);
    preorder(root.left);
    preorder(root.right)
}
// Non-recursive methods
const preorder2 = (root) = >{
    if(! root) {return; }const stack = [root];
    while(stack.length){
        const n = stack.pop();
        console.log(n.val);
        // Right is entered first and left is entered later
        if(n.right){
            stack.push(n.right);
        }
        if(n.left){
            stack.push(n.left);
        }
    }
}
preorder(bt)
// Print: 1245367
Copy the code

Middle order traversal calculation method (left root right)

Middle order traversal of the left subtree of the root node
Accessing the root node
Middle order traversal is performed on the right subtree of the root node

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,}}};const preorder = (root) = >{
    if(! root){return;
    }
    preorder(root.left);
    console.log(root.val);
    preorder(root.right)
}

const preorder2 = (root) = >{
    if(! root) {return; }const stack = [];
    let p = root;
    while(stack.length || p){
        while(p){
            stack.push(p);
            p = p.left;
        }
        const n = stack.pop();
        console.log(n.val);
        p = n.right;
    }
}

preorder(bt)
// Print: 4 2 5 1 6 3 7
Copy the code

After order traversal calculation method (root left and right)

A post-order traversal of the left subtree of the root node is performed
A post-order traversal is performed on the right subtree of the root node
Accessing the root node

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,}}};const preorder = (root) = >{
    if(! root){return;
    }
    preorder(root.left);
    preorder(root.right)
    console.log(root.val);
}
const preorder2 = (root) = >{
    if(! root) {return; }// Left/right root --> back in first out: root right/left
    const stack = [root];
    const outputStack = [];
    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);
    }

}
preorder(bt)
// Print: 4 5 2 6 7 3 1
Copy the code

LeetCode:104. Maximum depth of a binary tree

Their thinking

To find the maximum depth, consider using depth-first traversal
In the depth-first traversal process, record the level of each node and find the largest level

The problem solving steps

Create a new variable to record the maximum depth
Depth-first traverses the entire tree, recording the hierarchy of each node while constantly refreshing the maximum depth variable
Return the maximum depth variable at the end of the traversal

The problem solving coding:

/** * 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 maxDepth = function(root) {
    let res = 0;
    const dfs = (n , len) = >{
        if(! n){return ;
        }
        if(! n.left && ! n.right){ res =Math.max(res,len);
        }
        dfs(n.left, len + 1);
        dfs(n.right, len + 1);
    }
    dfs(root,1);
    return res;
};
Copy the code

LeetCode:111. Minimum depth of binary tree

Their thinking

To find the minimum depth, consider using breadth-first traversal
During breadth-first traversal, when a leaf node is encountered, the traversal is stopped and the node level is returned

The 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

The problem solving coding:

/** * 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 minDepth = function(root) {
    // breadth-first traversal + hierarchy
    if(! root){return 0;
    }
    let q = [[root,1]].while(q.length){
        let [n,len] = q.shift();
        if(! n.left && ! n.right){return len;
        }
        if(n.left){
            q.push([n.left,len+1])}if(n.right){
            q.push([n.right,len+1])}}};Copy the code

LeetCode:102. Sequence traversal of binary trees

Their thinking

The sequence traversal order is breadth-first traversal
However, the hierarchy of the current node needs to be recorded during traversal so that it can be added to different arrays

The problem solving steps

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

The problem solving Coding:

/** * 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[][]}* /
/ / method
var levelOrder2 = function(root) {
    if(! root){return[]}let q = [[root,0]].const res = [];
    while(q.length){
        const [n,level] = q.shift();
        if(! res[level]){ res.push([n.val]); }else{
            res[level].push(n.val);
        }
        n.left && q.push([n.left,level + 1]);
        n.right && q.push([n.right,level + 1]);
    }
    return res;

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

LeetCode:94. Middle order traversal of binary trees

Middle order traversal (left middle right)

/** * 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[]}* /
/ * * recursion * /
var inorderTraversal = function(root) {
    const res = [];
    const inorder = (root) = > {
        if(! root) {return;
        }
        inorder(root.left);
        res.push(root.val);
        inorder(root.right);
    }
    inorder(root);
    return res;
};
/ * / * * iteration
var inorderTraversal = function(root) {
    const res = [];
    const stk = [];
    while (root || stk.length) {
        while (root) {
            stk.push(root);
            root = root.left;
        }
        root = stk.pop();
        res.push(root.val);
        root = root.right;
    }
    return res;
};


Copy the code

Leetcode:112. Sum of paths

Their thinking

During depth-first traversal, the sum of the node values of the current path is recorded
At the leaf node, determine whether the sum of the node values of the current path equals the target value

The problem solving steps

Depth first traverses binary tree. At leaf nodes, judge whether the sum of node values of the current path equals the target value, and return true if so
If there is no match, false is returned

The problem solving coding

/** * 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
 * @param {number} targetSum
 * @return {boolean}* /
var hasPathSum = function(root, targetSum) {
    if(! root){return false;
    }
    let res = false;
    const dfs = (n,val) = >{
        if(! n.left && ! n.right && val === targetSum){ res =true;
        }
        n.left && dfs(n.left, val + n.left.val);
        n.right && dfs(n.right, val + n.right.val);
    }
    dfs(root,root.val);
    return res;
};
Copy the code

Front-end and tree: Traverses all node values of JSON

const json = {
    a: {b: {c:1}},
    d: [1.2]};const dfs = (n,path) = >{
    console.log(n,path);
    Object.keys(n).forEach(k= >{
        console.log(k)
        dfs(n[k],path.concat(k));
    })
}
dfs(json,[])
Copy the code

Tree introduction

What is depth/breadth first traversal?

Depth-first traversal algorithm solution

Breadth-first traversal algorithm solution

What is a binary tree

Sequential traversal method (root left and right)

Middle order traversal calculation method (left root right)

After order traversal calculation method (root left and right)

LeetCode:104. Maximum depth of a binary tree

LeetCode:111. Minimum depth of binary tree

LeetCode:102. Sequence traversal of binary trees

LeetCode:94. Middle order traversal of binary trees

Leetcode:112. Sum of paths

Front-end and tree: Traverses all node values of JSON

Related Posts

How do I read the source code

Ultimate pursuit, let small program code independently reduce 10% of plug-in P-CSS-modules

Summary of successful use of Vite in VUE2 environment!!