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  <p>Verwandte Empfehlungen:</p><p class="comments-box-content"><a href="http://www.php.cn/js-tutorial-406764.html" target="_blank" title="js中字符串的全排列的算法解析">Algorithmusanalyse der vollständigen Anordnung von Zeichenfolgen in js</a><br></p><p class="mt20 ad-detail-mm hidden-xs"><a href="http://www.php.cn/js-tutorial-406767.html" target="_blank" title="js如何实现将上传图片并且压缩的方法">Wie js die Methode zum Hochladen und Komprimieren von Bildern implementiert </a><br></p>

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!