Analyse des Algorithmus zur Rekonstruktion von Binärbäumen mit js

Dieser Artikel stellt Ihnen die Analyse des Algorithmus zur Rekonstruktion von Binärbäumen mit js vor. Er hat einen gewissen Referenzwert.

Problembeschreibung

Geben Sie die Ergebnisse der Durchquerung vor der Bestellung und der Durchquerung in der Reihenfolge eines Binärbaums ein. Bitte rekonstruieren Sie den Binärbaum. Gehen Sie davon aus, dass die Ergebnisse der eingegebenen Durchquerung vor der Bestellung und der Durchquerung in der Reihenfolge keine wiederholten Zahlen enthalten. Wenn Sie beispielsweise die Durchlaufsequenz vor der Reihenfolge {1,2,4,7,3,5,6,8} und die Durchlaufsequenz in der Reihenfolge {4,7,2,1,5,3,8} eingeben ,6}, rekonstruieren Sie dann den Binärbaum und kehren Sie zurück.

Analyse

Durchquerung vor der Ordnung ist die Reihenfolge von links, Mitte und Durchquerung mittlerer Ordnung ist die Reihenfolge von links, Mitte, rechts, dann für {1,2,4,7 ,3,5,6,8 } und {4,7,2,1,5,3,8,6}, 1 ist der Wurzelknoten, und dann teilt 1 die Durchlaufsequenz in der richtigen Reihenfolge in zwei Teile: „4 , 7, 2“ ist 1 Die Knoten im linken Teilbaum, „5, 3, 8, 6“ sind die Knoten im rechten Teilbaum von 1, die rekursiv zerlegt werden können

Code-Implementierung

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

Verwandte Empfehlungen:

Algorithmusanalyse der vollständigen Anordnung von Zeichenfolgen in js

Wie js die Methode zum Hochladen und Komprimieren von Bildern implementiert

Das obige ist der detaillierte Inhalt vonAnalyse des Algorithmus zur Rekonstruktion von Binärbäumen mit js. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!