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 <p>関連する推奨事項: </p><p class="comments-box-content"><a href="http://www.php.cn/js-tutorial-406764.html" target="_blank" title="js中字符串的全排列的算法解析">完全な配置のアルゴリズム分析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如何实现将上传图片并且压缩的方法">画像をアップロードして圧縮するメソッドをjsで実装する方法</a><br></p>

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