Location>code7788 >text

[JavaScript] Front-end algorithmic problems (reconstructing binary trees, reverse outputting each node of a chain table)

Popularity：310 ℃/2024-07-30 00:41:50

preamble

I reviewed some front-end algorithmic problems today and wrote about one or two of the more interesting ones: reconstructing a binary tree, reverse outputting each node of a chained table

title

Reconstruct a binary tree: Input the result of a leading and middle order traversal of a binary tree. Assume that neither the preceding nor the intermediate traversal result contains duplicate numbers. For example, if you enter the sequence {1,2,4,7,3,5,6,8} and the sequence {4,7,2,1,5,3,8,6}, then rebuild the binary tree and return it.

reasoning

Pre-order traversal (root left-right) and middle-order traversal (root left-right)

The idea is to use recursion to divide him into each small binary tree, and then all according to the characteristics of the first order traversal (root left and right) and the middle order traversal (left root right), the first element of the first order is the root, and then to find the root of the middle order, the root of the left is the left and right edges is the right, and then recursion until the first order is null when the representative of the root node is no longer, and then this element is the tail node

I.

①[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6] -> val=>1 ->L([2,4,7],[4,7,2]) & R([3,5,6,8],[5,3,8,6]) Root node 1 ,with left and right nodes

II.

①L([2,4,7],[4,7,2]) -> val=>2 ->L([4,7],[4,7]) & & & R(null , null) Root node 2 (left node of genus 1) ,with left node, no right node

② R([3,5,6,8],[5,3,8,6]) -> val=>3 ->L([5],[5]) && R([6,8],[6,8]) Root node 3 (the right node of genus 1) ,with left and right nodes

III.

①L([4,7],[4,7]) ->val=>4 -> L(null , null) && R([7],[7]) Root node 4 (left node of genus 2) ,with right node, no left node

② R([6,8],[8,6]) -> val=>6 -> L([8] , [8]) & & & R(null , null) Root node 6 (right node of genus 3), with left node, no right node

③ L([5],[5]) -> val=>5->(null,null)-> termination End node 5 (left node of genus 3)

IV.

①R([7],[7]) -> val=>7 -> termination Tail node 7 (right node of genus 4)

② L([8],[8]) -> val=>8 -> termination End node 8 (left node of genus 6)

code implementation

function rebuildBinaryTree(front, center) {
    // Determine if the node is empty
    if (!front || == 0) {
        return null; }
    }
    // Root node
    var TreeNode = {
        val: front[0]
    };
    for (var i = 0; i < ; i++) {
        // Find the middle-order traversal root node position
        if (center[i] === front[0]) {
            //Middle order traversal (left root right)
            //nodes to the left of the root node are to the left of that node
             = rebuildBinaryTree((1, i + 1), (0, i));
            // The node to the right of the root node is the right side of that node
             = rebuildBinaryTree((i + 1), (i + 1));
        }
    }
    return TreeNode.
}
let tree = rebuildBinaryTree([1, 2, 4, 7, 3, 5, 6, 8], [4, 7, 2, 1, 5, 3, 8, 6])
(tree)

title

Print Chained Table from End to End: Input a chained table and print the value of each node of the chained table from end to end.

reasoning

Since a chained table is unidirectional, we can't just start traversing backwards from the head node.

So you can use an array to simulate a stack. Iteratively traverse the chained table, press each node of the chained table into the stack, and then pop it off the stack in turn and print it.

code implementation

// Define a node class with the structure data representing the node data and next representing a pointer to the next node.
class Node {
    constructor(data) {
         = data
         = null
    }
}

function printNode(node) {
    // Define an array to represent the simulation stack
    let stack = new Array()
    // Initialize the current node as the incoming node
    let NodeNextElm = node
    // Determine if the next node pointer is empty
    while (NodeNextElm ! == null) {
        // Press the stack
        ()
        //store the pointer to the next node
        NodeNextElm =
    }
    while ( > 0) {
        //When the stack is not empty, the loop pops the top element of the stack and prints it
        (())
    }
}
//Initialize the chain table
// Create a new chain table node
const node1 = new Node(1)
const node2 = new Node(2)
const node3 = new Node(3)
// Manually store the pointer to the next node
 = node2
 = node3
// Call
printNode(node1)

process analysis

I. Enter, at this point, NodeNextElm: {
    "data": 1,
    "next": {
        "data": 2,
        "next": {
            "data": 3,
            "next": null
        }
    }
}

This enters the while loop:

① First loop:

Stack:[1]

NodeNextElm:{
"data": 2,
"next": {
"data": 3,
"next": null
}
}

② Second loop:

Stack stack:[1,2]

NodeNextElm:{
"data": 3,
"next": null
}

(iii) Third loop:

Stack: [1,2,3]

NodeNextElm:null

End of loop

pop() pops the stack and prints: 3, 2, 1

The above is a personal collation of content, the level is limited, if there is any error, I hope you gardeners do not begrudge advice! If you think it's good, please support it with a like and a follow! Thank you~๑-́₃-̀๑ [flower][flower][flower][flower].

<Previous Next>