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