Analysis of the algorithm for reconstructing binary trees using js

This article introduces to you the analysis of the algorithm for reconstructing binary trees using js. It has certain reference value. Friends in need can refer to it.

Problem Description

Enter the results of pre-order traversal and in-order traversal of a binary tree, please reconstruct the binary tree. It is assumed that the results of the input pre-order traversal and in-order traversal do not contain repeated numbers. For example, if you input the pre-order traversal sequence {1,2,4,7,3,5,6,8} and the in-order traversal sequence {4,7,2,1,5,3,8,6}, then reconstruct the binary tree and return.

Analysis

Pre-order traversal is in the order of left, center, and mid-order traversal is the order of left, center, and right. Then for {1,2,4,7,3,5,6,8 } and {4,7,2,1,5,3,8,6}, 1 is the root node, and then 1 divides the in-order traversal sequence into two parts, "4, 7, 2" is 1 The nodes on the left subtree, "5, 3, 8, 6" are the nodes on the right subtree of 1, which can be decomposed recursively

Code implementation

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
    var root = recon(0, pre.length-1, pre, 0, vin.length-1, vin);
    return root;
}

function recon(preStart, preEnd, pre, vinStart, vinEnd, vin){
    if(preStart > preEnd || vinStart > vinEnd) {
        return null;
    }

    var node = new TreeNode(pre[preStart]);

    for(var i = vinStart;i <= vinEnd;i++) {
        if(vin[i] === pre[preStart]){
            node.left = recon(preStart+1, preStart+i-vinStart, pre, vinStart, i-1, vin);
            node.right = recon(preStart+i-vinStart+1, preEnd, pre, i+1, vinEnd, vin);
        }
    }

    return node;
}

Related recommendations ：

Algorithm analysis of the full arrangement of strings in js

How js implements the method of uploading and compressing images

The above is the detailed content of Analysis of the algorithm for reconstructing binary trees using js. For more information, please follow other related articles on the PHP Chinese website!