Analyse de l'algorithme de reconstruction des arbres binaires à l'aide de js

Cet article vous présente l'analyse de l'algorithme de reconstruction des arbres binaires à l'aide de js. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Description du problème

Entrez les résultats du parcours en pré-ordre et du parcours en ordre d'un arbre binaire, veuillez reconstruire l'arbre binaire. Supposons que les résultats du parcours de pré-ordre d'entrée et du parcours dans l'ordre ne contiennent pas de nombres répétés. Par exemple, si vous saisissez la séquence de parcours en pré-ordre {1,2,4,7,3,5,6,8} et la séquence de parcours en ordre {4,7,2,1,5,3,8 ,6}, puis reconstruisez l'arbre binaire et revenez.

Analyse

Le parcours de pré-ordre est l'ordre de gauche, centre et le parcours d'ordre intermédiaire est l'ordre de gauche, milieu, droite, puis pour {1,2,4,7 ,3,5,6,8 } et {4,7,2,1,5,3,8,6}, 1 est le nœud racine, puis 1 divise la séquence de parcours dans l'ordre en deux parties, "4 , 7, 2" vaut 1. Les nœuds du sous-arbre de gauche, "5, 3, 8, 6" sont les nœuds du sous-arbre de droite de 1, qui peuvent être décomposés de manière récursive

Implémentation du code

/* 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;
}

Recommandations associées :

Analyse algorithmique de l'arrangement complet des chaînes en js

Comment js implémente la méthode de téléchargement et compresser des images

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!