jsを用いた二分木再構成アルゴリズムの解析

この記事では、js を使用してバイナリ ツリーを再構築するアルゴリズムの分析を紹介します。必要な方は参考にしてください。

問題の説明

二分木の事前順走査と順走査の結果を入力して、二分木を再構築してください。入力の事前順序トラバーサルと順序内トラバーサルの結果には、繰り返しの数値が含まれていないと仮定します。たとえば、前順走査シーケンス {1,2,4,7,3,5,6,8} と順走走査シーケンス {4,7,2,1,5,3,8 を入力した場合,6}、次にバイナリ ツリーを再構築して戻ります。

分析

前順トラバーサルは左、中央、中順トラバーサルは左、中央、右の順序で、その後、{1,2,4,7,3,5,6,8 が対象となります} と {4,7,2 ,1,5,3,8,6}、1 はルート ノード、次に 1 は順番の走査シーケンスを 2 つの部分に分割します。「4, 7, 2」がノードです1 の左側のサブツリーの「5、3、8、6」は、1 の右側のサブツリーのノードであり、再帰的に分解できます

コード実装

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

関連する推奨事項:

完全な配置のアルゴリズム分析jsの文字列の説明

画像をアップロードして圧縮するメソッドをjsで実装する方法

以上がjsを用いた二分木再構成アルゴリズムの解析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。