PreOrderとInOrderでバイナリツリーを復元する - Javascript

Question

誰かがProrderとInorderの配列を使ってバイナリツリーを復元する方法を教えてもらえますか？私はいくつかの例を見てきましたが（JavaScriptはありません）、それは意味がありますが、再帰呼び出しは試してみると完全なツリーを返すことはありません。説明を見るのが大好きです。ここでオフを開始するためにいくつかのコードです：ツリーノードがこれを使用して作成

：ツリーを作成する

function Tree(x) { 
    this.value = x; 
    this.left = null; 
    this.right = null; 
} 

はこれを使用しています。

function retoreBinaryTree(inorder, preorder) { 

} 

いくつかのサンプル入力：

inorder = [4,2,1,5,3] 
preorder = [1,2,4,3,5,6] 

inorder = [4,11,8,7,9,2,1,5,3,6] 
preorder = [1,2,4,11,7,8,9,3,5,6] 

をEDIT私は数日間この作業をしていたし、wを出すことができませんでした私自身の解決策で、私はいくつかを探し出した（ほとんどはJavaで書かれていた）。私はthis solutionを模倣しようとしたが、役に立たなかった。

Answer 1

これは、私はあなたが問題なく変換することができると思うC++における解決策されています、あなたは何を

/* keys are between l_p and r_p in the preorder array 

    keys are between l_i and r_i in the inorder array 
*/ 
Node * build_tree(int preorder[], long l_p, long r_p, 
      int inorder[], long l_i, long r_i) 
{ 
    if (l_p > r_p) 
    return nullptr; // arrays sections are empty 

    Node * root = new Node(preorder[l_p]); // root is first key in preorder 
    if (r_p == l_p) 
    return root; // the array section has only a node 

    // search in the inorder array the position of the root 
    int i = 0; 
    for (int j = l_i; j <= r_i; ++j) 
    if (inorder[j] == preorder[l_p]) 
     { 
     i = j - l_i; 
     break; 
     } 

    root->left = build_tree(preorder, l_p + 1, l_p + i, 
       inorder, l_i, l_i + (i - 1)); 
    root->right = build_tree(preorder, l_p + i + 1, r_p, 
       inorder, l_i + i + 1, r_i); 

    return root; 
}